堆

堆的应用场景非常多,最经典的是 堆排序,原地排序,O(nlogn)

快速排序平均情况下时间复杂度也为O(nlogn),快速排序比堆排序好,为什么呢?

堆(Heap) 必须满足两个条件:

1. 完全二叉树,除最后一层其他层节点都是满节点,最后一层节点必须靠左.

2. 大顶堆,堆中每个节点的值 必须 大于等于 其子树中每个节点的值

或

2. 小顶堆,堆中每个节点的值 必须 小于等于 其子树中每个节点的值

实现一个堆

完全二叉树适合使用 数组储存,节省空间,不需要指针,单纯通过下标

跳过下标0,从下标1开始存放,i的左子节点为i*2,右子节点为i*2+1

插入一个元素

堆化,插入数据后进行调整,使其重新满足堆的特性

堆化 有两种,从下往上,从上往下

从下往上的堆化,

节点插入末尾,与父节点比较大小,不满足堆条件就交换两个节点,重复这个过程

删除堆顶元素

大顶堆 堆顶为最大元素,小顶堆 堆顶为最小元素.

如果直接移除堆顶元素,再从上往下找补位,会使数组出现空洞,破坏完全二叉树

删除堆顶元素思路:

1. 交换堆顶元素与数组最后一个元素

2. 删除最后一个元素

3. 自上而下堆化,每轮 当前最大的数,就在 左子/右子/当前节点 其中之一

class Heap {
    constructor() {
        this.store = []
    }
    insert(data) {
        this.store.push(data)
        heapify(a, this.store.length - 1)
    }
    heapify(i) {
        while (i / 2 > 0 && this.store[i] > this.store[i / 2]) {
            swap(this.store, i, i / 2);
            i = i / 2;
        }
    }
    removeMax() {

    }
}

堆排序

建堆

排序