堆的概念
- 大顶堆和小顶堆:
- 大顶堆:任意的三元组,父节点都大于两个子节点。
- 小顶堆:任意的三元组,父节点都小于两个子节点。
- 根节点为最大值或最小值。
堆的基本操作(以大顶堆为例)
- 尾部插入
- 比父节点大就和父节点交换 递归向上调整
- 这个过程称为SHIFT-UP
- 头部弹出
- 用最后一个元素(叶子结点)补位 递归向下调整
- 这个过程称为SHIFT-DOWN
// 大顶堆代码实现
#define MAX_N 1000
int data[MAX_N + 5], cnt = 0;
void shift_up(int ind) {
// 从二叉树的子节点坐标找到其父节点坐标:(ind - 1) / 2
while (ind && data[(ind - 1) / 2] < data[ind]) {
swap(data[ind], data[(ind - 1) / 2]);
ind = (ind - 1) / 2;
}
return;
}
void shift_down(int ind) {
// n:最大子节点坐标
int n = cnt - 1;
// ind一定有子节点时
while (ind * 2 + 1 <= n)
{
int temp = ind; // temp: 指向三元组中最大值的下标
// 和左子节点比较: 小于左子节点
if (data[temp] < data[ind * 2 + 1]) temp = ind * 2 + 1;
// 和右子节点比较: 存在右子节点 && 小于右子节点
if (ind * 2 + 2 <= n && data[temp] < data[ind * 2 + 2]) temp = ind * 2 + 2;
// 判断ind是否是当前三元组中的最大值: 结束循环
if (temp === ind) break;
swap(data[ind], data[temp]);
ind = temp;
}
return;
}
void push(int x) {
data[cnt++] = x;
// 尾部元素上升:新插入的最后一位元素 与其父节点比较 递归上升
shift_up(cnt - 1);
return;
}
void pop() {
if (size() === 0) return;
// 交换头部元素和尾部元素
swap(data[0], data[cnt - 1]);
// 将数组范围 减去最后一位元素
cnt -= 1;
// 头部元素下降
shift_down(0);
return;
}
int top() {
return data[0];
}
int size() {
return cnt;
}