堆 Heap
堆是计算机科学中的一种特别的树状数据结构。
定义：给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值。
若父节点的值恒小于等于子节点的值，此堆称为小根堆或小顶堆。
若父节点的值恒大于等于子节点的值，此堆称为大根堆或大顶堆。
在堆中最顶端的那一个节点，称为根节点，根节点本身没有父节点。
可以迅速找到一堆数中的最大或最小值的数据结构。
常见的堆有二叉堆、斐波那契堆等。
在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题而设计的一种数据结构。
二叉堆是堆（优先队列 priority queue）的一种常见且简单的实现；但并不是最优的实现。
不同实现的比较：https://en.wikipedia.org/wiki/Heap_(data_structure)
性质
堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均为该数据结构的这种实现。这种数据结构具有以下性质
任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆续性）。
堆总是一颗完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
将根节点最大的堆叫最大堆或大根堆，根节点最小的堆叫最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
二叉堆实现细节
二叉堆一般都通过“数组”来实现
假设“第一个元素”在数组中的索引为 0 的话，则父节点和子节点的位置关系如下：
根节点（顶堆元素）是：a[0]
索引为 i 的左孩子的索引是 (2*i + 1)
索引为 i 的右孩子的索引是 (2*i + 2)
索引为 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)
