堆的性质
- 堆是一种满足特定条件的完全二叉树 (小顶堆：任意节点的值 <= 其子节点的值；大顶堆：任意节点的值 >= 其子节点的值)
- 最底层节点靠左填充，其他层节点都被填满（完全二叉树的性质）
- 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的
INFO
许多编程语言提供的是优先队列，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列 从使用角度来看，可以将“优先队列”和“堆”看作等价的数据结构 在Java中可以认为堆就是优先级队列，优先级队列就是堆，其他语言不行。
DANGER
也有不属于完全二叉树的堆，比如二项堆、斐波那契堆
堆的操作
元素入堆
把新加的元素添加到堆底，【从底至顶】执行堆化
堆顶元素出堆
- 交换堆顶元素和堆底元素
- 删除堆底元素
- 【从顶至底】执行堆化
WARNING
以下针对大顶堆（小顶堆符号反过来）
- 【从底至顶堆化】
- 传入堆化节点的索引i
- 获取该节点i的父节点索引p
2.1. 如果p<0，说明越过根节点了，堆化停止
2.2. 如果当前节点的值<父的值，节点关系不用修复，堆化停止 - 否则，交换p节点和i节点的值
- 将i更新为p，向上继续堆化（为什么是向上？因为p是父节点索引）
- 【从顶至底堆化】
- 传入堆化节点的索引i
- 获取左子节点索引l和右子节点索引r
- 找出l、r，i对应的值中最大的
- 如果最大的值是i对应的值，节点关系不用修复，堆化停止
- 否则，交换i节点和最大值节点的值
- 将i更新为最大值节点的索引，向下继续堆化（为什么是向下，因为i更新为子节点索引）
堆的使用技巧
查找：找(k)大用小(顶堆)，(后序元素比根)大的进(堆)；找小用大，小的进
排序：升序用小，降序用大
大顶堆代码示例