目录
- 堆
- 定义堆
- 建堆（以大顶堆为例）
- 删除堆顶元素
- 插入元素
- 堆排序
- 排序思路
- 代码实现
堆
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子结点的值。
- 大顶堆：父亲结点的值大于或等于孩子结点的值。
- 小顶堆：父亲结点的值小于或等于孩子结点的值。
定义堆
- 使用数组来存储完全二叉树，结点按层序存储于数组中，其中第一个结点将存储于数组中的1号位，并且数组 i 号位表示的结点的左孩子就是 2i 号位，而右孩子则是（2i+1）号位。
#define MaxSize 1000
// heap为堆,n为元素个数
int heap[MaxSize], n = 10;
建堆（以大顶堆为例）
对一个给定的初始序列，用向下调整的思路构建大顶堆：
- 总是将当前结点V与它的左右孩子比较（如果有的话）。
- 假如孩子中存在权值比结点V的权值大的，就将其中权值最大的那个孩子结点与结点V交换。
- 交换完毕后继续让结点V和孩子比较，直到结点V的孩子的权值都比结点V的权值小或是结点V不存在孩子结点。
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// 对heap数组在[low,high]范围进行向下调整
// 其中low为欲调整结点的数组下标,high一般为堆的最后一个元素的数组下标
void downAdjust(int low, int high) {
int i = low, j = i * 2; // i为欲调整结点,j为其左孩子
while (j <= high) { // 存在孩子结点
// 如果右孩子存在,且右孩子的值大于左孩子
if (j + 1 <= high && heap[j + 1] > heap[j])
j = j + 1; // 让j存储右孩子下标
// 如果孩子中最大的权值比欲调整结点i大
if (heap[j] > heap[i]) {
swap(&heap[j], &heap[i]); // 交换最大权值的孩子与欲调整结点
i = j; // 保持i为欲调整结点
j = i * 2; // j为i的左孩子
} else
break; // 孩子的权值均比欲调整结点i小,则无需向下调整
}
}
- 假设序列中元素的个数为n，由于完全二叉树的叶子结点个数为ceiling(n/2)，因此数组下标在[1，floor(n/2)]范围内的结点都是非叶子结点。
- 从floor(n/2)号位开始倒着枚举结点，对每个遍历到的结点i进行[i，n]范围的调整。
- 这样每次调整完一个结点后，当前子树中权值最大的结点就会处在根结点的位置，保证了每个结点都是以其为根结点的子树中的权值最大的结点。
建堆代码如下，时间复杂度为O(n)。
// 建堆
void createHeap() {
for (int i = n / 2; i >= 1; --i)
downAdjust(i, n);
}
删除堆顶元素
删除堆顶元素，即删除堆中最大的元素（大顶堆），并让其仍然保持堆的结构。
- 用最后一个元素覆盖堆顶元素。
- 对根结点进行向下调整。
代码如下，时间复杂度为O(logn)。
// 删除堆顶元素
void deleteTop() {
heap[1] = heap[n--]; // 用最后一个元素覆盖堆顶元素,并让元素个数减1
downAdjust(1, n); // 向下调整堆顶元素
}
插入元素
向堆中插入一个元素，并让其仍然保持堆的结构。
- 把要插入的元素放在数组的最后（也就是完全二叉树的最后一个结点后面）。
- 然后进行向上调整操作：把欲调整结点与父亲结点比较，如果权值比父亲结点大，那么就交换其与父亲结点。
- 这样反复比较，直到到达堆顶或是父亲结点的权值较大为止。
- 向上调整的时间复杂度为O(logn)。
代码如下。
// 对heap数组在[low,high]范围进行向上调整
// 其中low一般设置为1,high表示欲调整结点的数组下标
void upAdjust(int low, int high) {
int i = high, j = i / 2; // i为欲调整结点,j为其父亲结点
while (j >= low) { // 父亲结点在[low,high]范围内
// 父亲权值小于欲调整结点i的权值
if (heap[j] < heap[i]) {
swap(&heap[j], &heap[i]); // 交换父亲结点和欲调整结点
i = j; // 保持i为欲调整结点
j = i / 2; // 保持j为i的父亲
} else
break; // 父亲的权值比欲调整结点i的权值大,调整结束
}
}
// 添加元素x
void insert(int x) {
heap[++n] = x; // 让元素个数加1,然后将数组末位赋值为x
upAdjust(1, n); // 向上调整新加入的结点n
}
堆排序
堆排序是指使用堆结构对一个序列进行排序。此处讨论大顶堆递增排序的情况。
排序思路
- 大顶堆建堆完毕后，堆顶元素是最大的。
- 取出堆顶元素，将堆的最后一个元素替换至堆顶。
- 针对堆顶元素，进行一次向下调整的操作。
- 重复②③，直至堆中只剩一个元素。
- 注意：
- 大顶堆排序完后，heap数组中的元素为升序；
- 小顶堆排序完后，heap数组中的元素为降序；
- 故升序建大顶堆，降序建小顶堆。
代码实现
- 倒着遍历数组（节省空间），访问到i号位时，将堆顶元素和i号位的元素交换。
- 接着在[1，i - 1]范围内对堆顶元素进行一次向下调整即可。
// 堆排序
void heapSort() {
createHeap(); // 建堆
for (int i = n; i > 1; --i) { // 倒着枚举，直到堆中只有一个元素
swap(&heap[i], &heap[1]); // 交换heap[i]与堆顶
downAdjust(1, i - 1); // 调整堆顶
}
}
