前言

说起堆这种数据结构，可能很多前端er并不清楚，堆到底是个什么东西，这种数据结构又有什么用呢？

其实，我也一样，虽然刷了不少的算法，但是每次遇到需要用 堆的时候，都是大概有那么点意思，可是那个意思又不多，你懂我意思吧~~~

这一节，我们就来总结一下堆相关的知识点并了解一下这种数据结构可以解决的问题，最起码之后如果遇到，不至于无从下手，进而可以自己去尝试实现一个堆这种数据结构。

概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆总是一棵完全二叉树。
• 堆中某个结点的值总是不大于或不小于其父结点的值；

上面是关于堆的概念，首先值的关注的点在于堆是一棵完全二叉树。

而所谓的完全二叉树，可以理解为一个非常规整的二叉树，比如有n个节点，那么这n个节点是会从左往右，从上往下，依次排列，只有当当前层的节点排满了，才会进行到下一层，继续从左往右排列。

举个例子：

根据上面的定义，这棵树是一棵完全二叉树吗？

显然不是的，这棵树的第二层并没有排满就往第三层去加节点了。我们需要为它增加两个节点即可让它成为一棵完全二叉树。

至此，我们对堆有了一个大概的概念，原来堆就长这样啊~

然后，我们注意到堆的第二条性质：堆中某个结点的值总是不大于或不小于其父结点的值。 换句话说，就是堆中的每个节点，都会与它的子节点存在一种关系：

• 如果每个节点都比它的子节点大，则这个堆，就被叫做大顶堆（堆顶是这一组数据的最大值）。
• 如果每个节点都比它的子节点小，则这个堆，就被叫做小顶堆（堆顶是这一组数据的最小值）。

构建堆

堆的概念我们了解了，接下来，就尝试构建一下堆吧。

这里，我们先为上面例子中的完全二叉树给按顺序标记上编号，看一看是什么样子的呢？

根据图中的标记，我们可以发现，每个节点和它的左右子节点会有一个非常明显的规律：

这个规律就是：

• 左子节点 = 父节点 * 2 + 1
• 右子节点 = 父节点 * 2 + 2

根据上面的分析，我们可以发现，这棵完全二叉树的编号就非常类似于数组的下标，那我们是不是就可以尝试用我们所熟悉的数组来表示完全二叉树，用数组来去构建堆呢？答案是肯定的。

接下来，我们开始一步步实现一个大顶堆（小顶堆同理的）。

容器

我们创建一个数组来作为容器。

class Heap {
    constructor() {
        this.arr = []
    }
}

插入

容器有了，接下来我们就是向容器中去插入元素。这里，关于插入元素，我们想要的是，每次执行完插入操作，都能让我们的堆仍然是一个大顶堆。

那具体要怎么实现呢？

• 我们可以首先将插入的元素放置数组的末尾
• 然后，每次去和它的父节点比较，如果该元素比父元素要大，那我们直接交换父子元素位置
• 之后，不断的重复这个过程，直到节点不再有父元素或者当前元素小于父元素，这一轮比较就到此为止，完成插入操作。
• 整个过程就类似于一个冒泡的操作，这里画个图可能会更清晰一些：

比如，我们有这样的数据，一个数组[1,3,4,6]，想它构建为一个大顶堆，那么整个构建的流程就是：

上面就是插入元素的整个冒泡过程，最后完成插入操作，得到的就是一个大顶堆。接下来，我们来将这个插入函数进行实现：

class Heap {
    constructor() {
        // 容器
        this.arr = []
    }
    
    // 插入
    insert(val) {
        // 首先将元素插入末尾
        this.arr.push(val)
        // 获取新插入元素的下标
        let index = this.arr.length - 1
        while(index > 0) {
            // 获取父元素下标
            let pIndex = Math.floor((index - 1) / 2)
            if(this.arr[index] > this.arr[pIndex]) {
                // 如果该元素大于父元素，则交换位置
                [this.arr[index],this.arr[pIndex]] = [this.arr[pIndex],this.arr[index]]
                index = pIndex
            }else{
                // 已经实现了大顶堆，跳出循环
                break
            }
        }
    }
}

至此，新元素我们已经可以完成插入，并且大顶堆我们也构建出来了。那这个大顶堆构建出来，有什么用呢？

最直观的，如果我们想取数组的最大元素，那么堆顶元素就是这个数组的最大元素。

可是倘若，我想要数组的第二大，第三大。。。的元素，阁下又当如何应对？

取出

既然是想取第二大的元素，那我们是不是就可以将堆顶的元素直接取出，然后重新构建大顶堆，再取堆顶元素呢？

具体我们可以这样操作：

• 将堆顶元素与末尾元素进行交换位置。
• 将末尾元素弹出。
• 此时的堆顶是我们之前的末尾元素，所以需要来一次从上而下的构建。
  • 比较当前元素和左右子元素的大小，如果左右子元素比当前元素大，那么将当前元素与左右子元素中的最大值进行交换位置，然后调整坐标，重复该过程，直到没有左右子元素或者当前元素不小于左右子元素为止。

仍然用上面的例子，如图：

通过上面的操作，我们就可以分别得出最大，第二大。。。第k大的元素啦~

接下来，我们将这个操作对应的函数来实现一下：

class Heap {
    constructor() {
        this.arr = []
    }
    
    // 插入
    insert(val) {
        //...
    }
    
    // 取出
    outVal() {
        // 容器里已没有元素
        if(this.arr.length === 0) return
        // 容器里只有一个元素，无须花里胡哨，直接取出即可
        if(this.arr.length === 1) return this.arr.pop()
        // 保存堆顶元素
        let max = this.arr[0]
        // 类似于交换堆首尾元素位置，弹出末尾元素
        this.arr[0] = this.arr.pop()
        let index = 0
        let l = index * 2 + 1
        let r = index * 2 + 2
        
        while(l < this.arr.length) {
            let tmp = l
            // 取左右子元素中最大值的下标
            if(r < this.arr.length && this.arr[r] > this.arr[l]) {
                tmp = r
            }
            // 如果子元素比当前元素大，则 交换位置
            if(this.arr[index] < this.arr[tmp]) {
                [this.arr[index], this.arr[tmp]] = [this.arr[tmp], this.arr[index]]
                index = tmp
                l = index * 2 + 1
                r = index * 2 + 2
            }else{
                // 跳出循环
                break
            }
        }
        return max
    }
}

至此，我们的大顶堆就已经构建完毕了。JYM可以尝试模仿大顶堆来自己实现一个小顶堆，也都是一样的。

应用

那么堆这种数据结构一般都用于解决什么问题呢？在算法题中，有一个很常见的题目类型——TopK问题。

TopK问题，一些题目中会给我们一组数据，让我们从中找出前K大或者第K大的数据，那么这种问题，用这一节介绍的大顶堆就会迎刃而解了~

来道力扣题目小试牛刀：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

这道题就是一个比较明显的TopK问题，只不过这里问的不是数值的大小，而是出现的频率。我们只需结合之前已经讲过的算法——哈希表即可解决这个问题。

前面构建大顶堆，我们遍历的是数组，这一次我们是先构建哈希表，然后遍历哈希表即可。有了前面的基础，想必解决这个问题也不在话下。这道题我把链接也给出来，可以尝试自己实现一下。

这里也放上我解题的完整代码，可以作为参考，其中大顶堆的实现就是在上面代码的基础上稍加改造即可：

var topKFrequent = function (nums, k) {
    // 构建频率的哈希表
    var m = new Map()
    for (var i = 0; i < nums.length; i++) {
        m.set(nums[i], (m.get(nums[i]) || 0) + 1)
    }
    // 这里大顶堆将哈希表作为参数传入构造函数
    // 因为我们比较的是频率，所以需要从哈希表中读取频率
    var heap = new Heap(m)
    m.forEach((val,key) => {
        heap.insert(key)
    })
    var ans = []
    for(var i = 0;i < k;i++) {
        ans.push(heap.outVal())
    }
    return ans
};

// 大顶堆
class Heap {
    constructor(m) {
        this.arr = []
        this.m = m
    }

    insert(key) {
        this.arr.push(key)
        let index = this.arr.length - 1
        while (index > 0) {
            let pIndex = Math.floor((index - 1) / 2)
            // 从哈希表中读取频率进行比较
            if (this.m.get(this.arr[index]) > this.m.get(this.arr[pIndex])) {
                [this.arr[index], this.arr[pIndex]] = [this.arr[pIndex], this.arr[index]]
                index = pIndex
            } else {
                break
            }
        }
    }

    outVal() {
        if (this.arr.length === 0) return
        if (this.arr.length === 1) return this.arr.pop()
        let max = this.arr[0]
        this.arr[0] = this.arr.pop()
        let index = 0
        let l = index * 2 + 1
        let r = index * 2 + 2
        while (l < this.arr.length) {
            let tmp = l
            if (r < this.arr.length && this.m.get(this.arr[r]) > this.m.get(this.arr[l])) {
                tmp = r
            }
             // 从哈希表中读取频率进行比较
            if (this.m.get(this.arr[index]) < this.m.get(this.arr[tmp])) {
                [this.arr[index], this.arr[tmp]] = [this.arr[tmp], this.arr[index]]
                index = tmp
                l = index * 2 + 1
                r = index * 2 + 2
            } else {
                break
            }
        }
        return max
    }
}