参考资料

定义

二叉堆是一种满二叉树，分为最大堆和最小堆。二叉树使用数组来进行

操作

插入

新插入的元素需要放在二叉树的最末端，然后不断地与父节点做比较，直到符合条件。

因此时间复杂度为O(logn)

删除

二叉堆的删除指的是删除堆顶元素，需要移除堆顶元素，再将最末端的元素置于堆顶，然后不断地与叶子节点做比较，直到符合条件。插入和删除动的是最末端和最前端元素，这样做的原因是保证数组的一贯连续性。

因此时间复杂度为O(logn)

建堆

直观的做法是执行n次插入操作，这样时间复杂度为O(nlogn)。但是有更高级的算法可以在O(n)的时间复杂度内完成建堆（详见二叉堆的wiki），因此通常说建堆的时间复杂度为O(n)。

查看最高优先级的元素

只需要直接查看堆顶元素即可。

因此时间复杂度为O(1)。

应用

优先队列

优先队列是一种抽象的数据类型，而二叉堆则是它的具体实现。

wiki: 优先队列是计算机科学中的一类抽象数据类型。

可以使用二叉堆的插入实现入队，删除实现出队。

堆排序

堆排序就是不断地移除堆顶元素（把堆顶元素与最末端元素交换，把交换后的堆顶元素移出堆），然后顺序或逆序输出，即可完成排序。

所谓堆排序就是每次取堆的根结点为最大值，然后将最后一个节点作为根节点，进行堆调整，堆排序的时间等于建堆和进行堆调整的时间，所以堆排序的时间复杂度是O(nlog n + n) =O(nlog n)。

实现

由于可以通过代数上将二叉树与与数组做映射，因此使用数组来实现二叉堆。如上图所示，k节点的左孩子是2k节点，右孩子是2k+1节点。

维护堆的性质

// 维护堆的性质
// heap为需要维护的堆
// i为需要调整的节点
// heap_size为堆的大小（因为这里是数组实现的，大小不能实时改变，就只能通过传参的方式假装减小数组大小）
void maxHeapify(vector<int>& heap, int i, int heap_size) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int max = i;

    if (left < heap_size && heap[left] > heap[max]) {
        max = left;
    }
    if (right < heap_size && heap[right] > heap[max]) {
        max = right;
    }
    if (max != i) {
        swap(heap[i], heap[max]);
        maxHeapify(heap, max, heap_size); // 继续调整交换后的节点
    }
    // 隐含停止条件：i为叶子节点
}

建堆

void buildHeap(vector<int>& nums) {
    // 叶子节点不用调整，因为没有孩子，所以调整也没用
    // 从底到上进行调整
    for (int i = nums.size()/2; i >= 0; --i) {
        maxHeapify(nums, i, nums.size());
    }
}

删除元素

void delete() {
	swap(nums[heap_size - 1], nums[0]);
	// 将堆的大小减1，这里只是假的减去
	--heap_size; 
	// 从根进行调整
    maxHeapify(nums, 0, heap_size);
    return nums[heap_size - 1];
}

其它

另外，本文是在做力扣239. 滑动窗口最大值时学习写成的，该题目有用到二叉堆。