数据结构——大顶堆

基础

一、堆就是用数组实现的二叉树

堆常用方法：

构建优先队列
支持堆排序
快速找出集合中的最小值（或最大值）

分为：最大堆和最小堆，两者差异在于节点的排序方式，在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。

二、目的

将最大（最小）的节点放在最前面，从而进行快速的插入、删除等操作。在二叉树中搜索会很快，但是在堆中搜索会很慢。

注意：堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

大顶堆

parent(i) = Math.floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = left + 1

Node	Array index (i)	Parent index	Left child index	Right child index
10	0	-1	1	2
7	1	0	3	4
2	2	0	5	6
5	3	1	7	8
1	4	1	9	10

具体ts实现:

class MyHeap {
    myHeap: number[]
    flag: number
    size: number
    constructor(arr: number[] = [], type: string = 'MAX') {
        this.flag = type === 'MAX' ? 1 : -1
        this.myHeap = arr
        this.size = arr.length
        this.heapfiy()
    }
    /**
     * @description 堆化
     */
    heapfiy (): void {
        this.myHeap.unshift(null)
        const lastParentIndex = Math.floor(this.size / 2)
        for (let i = lastParentIndex; i > 0; i--) {
            this.shiftDown(this.myHeap, i, this.size)
        }
        this.myHeap.shift()
    }
    /**
     * @param arr  待检查数组
     * @param i    检查的起始下标
     * @param s 堆大小
     * @description 向下
     */
    shiftDown (arr: number[], i: number, s?: number): void {
        let size = s ? s : this.size
        let left = 2 * i
        let right = left + 1
        // 左右孩子中较大/较小的那一个
        let theFitOne = 0
        //无左右孩子节点
        if (left > size && right > size) {
            return
        }
        //只有左孩子节点
        if (left <= size && right > size) {
            theFitOne = left
        }
        //只有右孩子节点
        if (right <= size && left > size) {
            theFitOne = right
        }
        //同时有左右孩子节点
        if (left <= size && right <= size) {
            theFitOne = arr[left] * this.flag < arr[right] * this.flag ? right : left
        }
        if (arr[i] * this.flag < arr[theFitOne] * this.flag) {
            this.swap(arr, i, theFitOne)
            this.shiftDown(arr, theFitOne, size)
        }
    }
    /**
     * @param i 需要移动的元素节点索引
     * @description 将当前节点元素层层向上交换位置
     */
    shiftUp (arr: number[], i: number): void {
        const parent = Math.floor((i - 1) / 2)
        if (arr[i] * this.flag < arr[parent] * this.flag || parent <= 0) {
            return
        } else {
            this.swap(arr, i, parent)
            this.shiftUp(arr, parent)
        }
    }
    swap (arr: number[], i: number, j: number): void {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }
    /**
     * @param el 插入的元素
     * @description 返回插入好的堆
     */
    insert (el: number): number[] {
        this.myHeap.push(el)
        const i = this.myHeap.length - 1
        this.shiftUp(this.myHeap, i)
        this.size++
        return this.myHeap
    }
    /**
     * @description 弹出最值
     */
    pop (): number {
        const { myHeap } = this
        // 交换第一个和最后一个元素
        this.swap(myHeap, 0, myHeap.length - 1)
        myHeap.unshift(null)
        const top = myHeap.pop()
        this.shiftDown(myHeap, 1, myHeap.length - 1)
        myHeap.shift()
        this.size--
        return top
    }
    /**
    * @description 返回堆排序好的新数组，不影响原数组
    */
    sort (): number[] {
        const { myHeap } = this
        const arr = [...myHeap]
        arr.unshift(null)
        for (let j = arr.length - 1; j > 1; j--) {
            this.swap(arr, 1, j)
            this.shiftDown(arr, 1, j - 1)
        }
        arr.shift()
        return arr
    }
    /**
    * @description 用删除节点就返回最大值（最大堆）或者最小值（最小堆）
    */
    peek (): number {
        return this.myHeap[0]
    }
    
    /**
     * @param i 被替换元素的坐标
     * @param el 替换的内容
     * @description 替换指定位置的元素
     */
    replace (i: number, el: number): void {
        const { myHeap } = this
        let orgin = myHeap[i]
        myHeap.unshift(null)
        i = i + 1
        myHeap.splice(i, 1, el)
        if ((el > orgin && this.flag > 0) || (el < orgin && this.flag < 0)) {
            this.shiftUp(myHeap, i)
        } else {
            this.shiftDown(myHeap, i)
        }
        myHeap.shift()
    }
}

测试:

var arr = [7,5,8,4,9,3,2,6,2]
console.log(arr)
var minHeap = new MyHeap([...arr], 'MIN')
minHeap.peek()

leetCode

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight\
```js
function lastStoneWeight(stones) {
const sts = new MyHeap(stones, “MAX”);
while (sts.myHeap.length > 1) {
const one = sts.pop();
const two = sts.peek();
const diff = one - two;
if (diff > 0) {
sts.replace(0, diff);
} else {
sts.pop();
}
}

return sts.myHeap[0] || 0;
}

执行用时：96 ms, 在所有 TypeScript 提交中击败了32.08%的用户
内存消耗：40.5 MB, 在所有 TypeScript 提交中击败了24.53%的用户
= =! 还不如我之前两次提交呢
### 参考资料：
- [数据结构：堆（Heap）](https://www.jianshu.com/p/6b526aa481b1)
- [JS数据结构与算法之《堆》](https://zhuanlan.zhihu.com/p/144699737?utm_source=wechat_session&utm_medium=social&utm_oi=559769045767880704)

基础

一、 堆就是用数组实现的二叉树

二、 目的

具体ts实现:

测试:

leetCode

夏木なつき青あお

一、堆就是用数组实现的二叉树

二、目的