堆 Heap、二叉堆 Binary Heap

堆 Heap

• 堆是计算机科学中的一种特别的树状数据结构。

• 定义：给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值。

• 若父节点的值恒小于等于子节点的值，此堆称为小根堆或小顶堆。

• 若父节点的值恒大于等于子节点的值，此堆称为大根堆或大顶堆。

• 在堆中最顶端的那一个节点，称为根节点，根节点本身没有父节点。

• 可以迅速找到一堆数中的最大或最小值的数据结构。

• 常见的堆有二叉堆、斐波那契堆等。

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题而设计的一种数据结构。

二叉堆是堆（优先队列 priority queue）的一种常见且简单的实现；但并不是最优的实现。

不同实现的比较：https://en.wikipedia.org/wiki/Heap_(data_structure)

性质

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均为该数据结构的这种实现。这种数据结构具有以下性质

• 任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆续性）。

• 堆总是一颗完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫最大堆或大根堆，根节点最小的堆叫最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

二叉堆实现细节

1. 二叉堆一般都通过“数组”来实现

2. 假设“第一个元素”在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：

3. 1. 根节点（顶堆元素）是：a[0]

   2. 索引为 i 的左孩子的索引是 (2*i + 1)

   3. 索引为 i 的右孩子的索引是 (2*i + 2)

   4. 索引为 i 的父节点的索引是 floor((i -1) / 2);

• 函数 floor(x) 的功能是“向下取整”，或是“向下舍入”，即取不大于 x 的最大整数。比如 floor(1.1)、floor(1.9) 都返回 1。

支持的基本操作

操作	描述	时间复杂度
build	创建一个空堆	O(n)
insert	向堆中插入一个新元素	O(log n)
update	将新元素提升使其其符合堆的性质
get	获取当前堆顶元素的值	O(1)
delete	删除堆顶元素	O(log n)
heapify	使删除堆顶元素的堆再次成为堆

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

大顶堆常见操作

insert 插入操作（HeapifyUp）

• 新元素一律先插入到堆的尾部

• 自下而上调整子节点与父节点，称作 heapify-up：比较当前节点与父节点，不满足“堆性质”则交换，从而使得当前子树满足二叉堆的性质。

• O(logN) or O(1)

Delete Max 删除堆顶操作（HeapifyDown）

• 将堆尾元素替换到顶部（及堆顶被替代删除掉）

• 从上而下调整父节点与它的子节点，称作 heapify-down：对于最大堆，父节点如果小于具有最大值的子节点，则交换二者，直至当前节点与它的子节点满足“堆性质”为止。

• O(logN)

Find Max

• O(1)