堆的定义
堆(Heap) 是通常是一个可以被看作 完全二叉树 的 数组 对象。总是满足以下性质:
-
堆中某个结点的值总是不大于或不小于其父结点的值
- 不大于:大根堆;不小于:小根堆
-
堆总是一棵完全二叉树
-
具有 n 个结点,深度为
-
根据结点编号可以得出父结点、左右孩子
-
堆虽然是数组对象,但是它是非线性数据结构,相当于一维数组,有两个直接后继。对于任意结点
- 若 i = 1,则结点 i 是二叉树的根,无双亲;若 i >= 1,则双亲是 i/2
- 若 2i > n,则无左孩子,否则左孩子是 2i
- 若 2i + 1 > n,则无右孩子,否则右孩子是 2i + 1
1 | const int maxn = 100; |
i 也可以是 0 基的,则对应的双亲、左右孩子变为:(i - 1)/2、2i + 1、2i + 2
基本操作
堆的基本操作有:调整成堆(向下、向上)、建堆、插入、删除。下面以大根堆为例。
向下调整
总是将当前结点 V 与它的左右孩子进行比较,假如存在比 V 大的孩子,则将最大的孩子与 V 进行交换;交换完毕后,继续让结点 V 与孩子比较,直至 V 比它的孩子都大或者没有孩子了
1 | void downAdjust(int low, int high) { |
- 时间复杂度:
向上调整
从最下面的叶子结点开始往上调整:
1 | void upAdjust(int low, int high) { |
- 时间复杂度:
建堆
建堆的过程一般采用的向下调整的方式。假设有 n 个元素,由于完全二叉树的叶子结点为 ,因此下标从在 的都是非叶子结点,因此可以从 倒着枚举结点 i,进行 的调整。
- 倒着枚举可以保证当前子树的根结点是最大值,使得建堆正确
1 | void createHeap() { |
- 时间复杂度:
删除堆顶
删除堆顶较为简单,只需要将最后一个元素覆盖堆顶,然后重新向下调整堆
1 | void deleteTop() { |
- 时间复杂度:
插入
在向上调整的基础上,可以很容易实现插入元素:
1 | void insert(int x) { |
- 时间复杂度:
应用
- 堆排序:每次取出根结点,就能得到一个有序列了