写在前面
记录一下二叉堆和堆排序, 堆(二叉堆)作为一种基本数据结构, 常在lc周赛三题位置出现, 遇到了我只能干着急, 必须好好学一下了. 参考算法导论(第三版).
这里说的堆指的是数据结构(抽象概念), 而不是程序执行时候的堆区(内存实体)
二叉堆介绍
二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆1。
- 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。
- 当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。
实际使用时, 二叉堆表示为一个数组, 可以被看成近似的完全二叉树(叶结点从左下角开始)
在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树2（Complete Binary Tree）。
具有$n$个节点的完全二叉树的深度为$\log_2n+1$。深度为$k$的完全二叉树，至少有${\displaystyle 2^{\begin{aligned}k-1\end{aligned}}}$个节点，至多有${\displaystyle 2^{\begin{aligned}k\end{aligned}}-1}$个节点。
堆具有以下几种属性:
-
length: 二叉堆(数组)长度;
-
root: 根节点;
-
父节点/左子节点/右子节点: 设$i$表示任一节点下标(下标从$0$开始), 则 \(\begin{cases} Parent(i)=\lfloor (i-1)/2\rfloor;\\ Left(i)=2i+1;\\ Right(i)=2i+2; \end{cases}\)
-
最大堆(堆排序): \(arr[Parent(i)]\geq arr[i]\)
-
最小堆(优先队列): \(arr[Parent(i)]\leq arr[i]\)
下面的ASCII图来自Wikipedia1, 分别展示了小根堆和大根堆.
1 11
/ \ / \
2 3 9 10
/ \ / \ / \ / \
4 5 6 7 5 6 7 8
/ \ / \ / \ / \
8 9 10 11 1 2 3 4
堆化(heapify)
这里以大根堆为例. 如输入数组不满足堆的条件(根节点大于等于子节点), 则需要对数组进行堆化.
小根堆调整一下大小于号即可.
基本方法(递归调用)
void Max_Heapify(vector<int> &arr, int len, int i) {
// array index start with 0
int l = 2 * i + 1, r = 2 * i + 2;
int largest = i;
if (l < len and arr[l] > arr[largest]) largest = l;
if (r < len and arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
Max_Heapify(arr, len, largest);
}
}
其中,
arr是堆数组, 以引用方式传参使其可以原地修改;len是数组长度, 这里虽然不改变参数的值, 但是后面进行堆排序时候会用到的;i是待堆化(heapify)的结点索引, 一般取值为0;
首先根据上面的节点之间的关系公式计算左子节点和右子结点的编号, 然后当前节点分别与左子结点和右子节点值进行比较, 若不满足堆的条件就记录新的最大值, 最后交换最大值即可. 最后向下遍历(递归)直到都满足条件.
思路还是比较清晰, 因为用到了递归.
迭代法
这里因为用到了尾递归, 所以直接修改递归函数的最后一行中传值语句即可3.
void Max_Heapify(vector<int> &arr, int len, int i) {
bool done = false;
while (!done) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < len && arr[l] > arr[largest]) largest = l;
if (r < len && arr[r] > arr[largest]) largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
i = largest;
} else
done = true;
// break; // 也行
}
}
还有一种方法, 这里参考了4的代码, 感觉不如while循环来的直观,
void Max_Heapify(vector<int> &arr, int len, int i) {
int largest{}, tmp = arr[i];
for (; i * 2 < len; i = largest) {
largest = i * 2;
if (largest + 1 < len && arr[largest + 1] > arr[largest]) largest++;
if (arr[i] < arr[largest])
swap(arr[largest], arr[i]);
else
break;
}
}
这种方法把递归传值放在了for中, 跳出条件是i * 2 < len, 通过让largest++的方式完成左右子结点与当前节点的比较, 是相当巧妙的写法.
建堆
通过堆化数组来完成:
void Build_Max_Heap(vector<int> &arr) {
int n = arr.size();
for (int i = (n - 1) / 2; i >= 0; --i) Max_Heapify(arr, n, i);
}
排序
void Heap_Sort(vector<int> &arr) {
Build_Max_Heap(arr);
int n = arr.size();
for (int i = n - 1; i > 0; --i) {
swap(arr[0], arr[i]);
Max_Heapify(arr, i, 0);
}
}
这里的排序是原地操作, 即每次从堆化后的数组中”弹出”(用交换操作完成)一个最大值(根)放在最后, 一直到数组头.
需要注意的是, 在弹出根节点之后, 还需要调整其余的n-1结点的顺序, 使其仍保持堆的属性, 就是通过前面的Heapify完成的.
优先队列的增删改查实现
参考<算法导论>
基本类
class Heap { // 小根堆的基本实现
private:
vector<int> arr; // 存放元素
int len; // 长度, 直接使用vector的size()方法也可以, 但是每次都要调用比较慢
void Heapify(int i, int n); // 堆化数组, 仅用于删除节点
public:
Heap() : arr({}), len(0) {}
int top();
bool empty();
int size();
void push(int key);
void pop();
};
主要API
int Heap::top() { return arr[0]; }
bool Heap::empty() { return len == 0; }
int Heap::size() { return len; }
堆化
void Heap::Heapify(int i, int n) { // 这里的堆化与前面堆排序时候的一样
int smallest{i}, l{2 * i + 1}, r{2 * i + 2};
if (l < n && arr[l] < arr[smallest]) smallest = l;
if (r < n && arr[r] < arr[smallest]) smallest = r;
if (smallest != i) {
swap(arr[i], arr[smallest]);
Heapify(smallest, n);
}
}
插入节点
void Heap::push(int key) {
arr.emplace_back(key);
// 插入节点之后, 节点在最后一个位置, 需要调整到合适的位置满足堆的属性
// 反向遍历, 需要保证父节点不大于对应的子节点(通过交换实现)
for (int i{len++}; i > 0 && arr[(i - 1) / 2] > arr[i]; i = (i - 1) / 2)
swap(arr[(i - 1) / 2], arr[i]);
}
删除节点
void Heap::pop() {
if (len == 0) return;
arr[0] = arr[--len]; // 弹出队头元素(小根)
arr.pop_back();
// 执行堆化
Heapify(0, len);
}
完整实现: 基于类模板
template <typename T,
class Compare = less<T>>
class Priority_Queue { // 默认小根堆
vector<T> arr;
size_t len;
public:
Priority_Queue() : arr(), len() {}
int top() { return arr[0]; }
bool empty() { return len == 0; }
int size() { return len; }
void pop() {
if (len == 0) return;
arr[0] = arr[--len]; // 弹出队头元素
arr.pop_back();
int i{};
for (;;) { // Heapify, by iter
int tmp{i}, l{2 * i + 1}, r{2 * i + 2};
if (l < len && Compare()(arr[l], arr[tmp])) tmp = l;
if (r < len && Compare()(arr[r], arr[tmp])) tmp = r;
if (tmp != i) {
swap(arr[i], arr[tmp]);
i = tmp;
} else
break;
}
}
void push(int key) {
//
arr.emplace_back(key);
for (auto i{len++}; i > 0 && Compare{}(arr[i], arr[(i - 1) / 2]);
i = (i - 1) / 2)
swap(arr[(i - 1) / 2], arr[i]);
}
};
测试:
void t1() {
Priority_Queue<int> minHeap;
Priority_Queue<int, greater<>> maxHeap;
for (auto i : {1, 4, 9, 3, 6, 8, 5, 2, 99})
minHeap.push(i), maxHeap.push(i);
for (; !minHeap.empty(); minHeap.pop()) cout << minHeap.top() << " ";
cout << "\n"; // 1 2 3 4 5 6 8 9 99
for (; !maxHeap.empty(); maxHeap.pop()) cout << maxHeap.top() << " ";
cout << "\n"; // 99 9 8 6 5 4 3 2 1
}