堆的基础知识
完全二叉树(
complete binary tree)-堆、优先队列
1、编号为i的子节点：左孩子编号2i， 右孩子编号2i+1
2、可以用连续空间存储(数组)=》子节点和父节点编号有关系我们使用一个数组来模拟，这表示的是一个实际方面的数据结构，但是我们在思维方面上可以看成一个完全二叉树。
堆：基于完全二叉树的一种结构
- 大顶堆：任意的三元组之间，如果父节点的值都大于子节点的值（根节点是最大值）
- 小顶堆：任意三元组之间，如果父节点的值都小于子节点的值（根节点是最小值）
1
2
3
4
5
6
7
812 3
/\ / \
11 10 7 4
/\ /\ /\ /\
6 7 9 3 10 12 9 6
/\ /\
4 5 15 14
大顶堆 小顶堆
拓展
数据结构：结构定义(定义一种结构，定义它的性质) + 结构操作(维护这个性质)
- 数据结构：定义一种性质，并维护这种性质
- 堆：适合维护集合的最值
堆操作
- 堆–尾部插入调整–》向上调整
- 比父节点大的就和父节点交换 递归向上调整
- 这个过程称为SIFT-UP
- 堆–头部弹出调整–》向下调整
- 用最后一个元素(叶子节点)补位 递归向下调整
- 这个过程称为SIFT-DOWN
- 堆-》尾部插入，头部弹出->队列-》又不是普通队列(每次弹出都是最大值或最小值-》当成优先级的话，每次弹出的是优先级最高的元素)=》优先级队列
堆-优先队列
| 普通队列 | 优先队列 |
|---|---|
| 尾部入队 | 尾部可以插入 |
| 头部出队 | 头部可以弹出 |
| 先进先出 | 每次出队权值(最大/最小的元素) |
| 数组实现 | 数组实现，逻辑上看成一个堆 |
堆是优先队列的一种实现方式