8.1 堆
堆(heap)是一种满足特定条件的完全二叉树,主要可分为两种类型,如图 所示。
- 小顶堆(min heap):任意节点的值 ≤ 其子节点的值。
- 大顶堆(max heap):任意节点的值 ≥ 其子节点的值。
堆作为完全二叉树的一个特例,具有以下特性。
- 最底层节点靠左填充,其他层的节点都被填满。
- 我们将二叉树的根节点称为“堆顶”,将底层最靠右的节点称为“堆底”。
- 对于大顶堆(小顶堆),堆顶元素(根节点)的值是最大(最小)的。
8.1.1 堆的常用操作
堆通常用于实现优先队列,大顶堆相当于元素按从大到小的顺序出队的优先队列。
8.1.2 堆的实现
下文实现的是大顶堆。
1. 堆的存储与表示
堆是一种完全二叉树,用数组来存储堆
当使用数组表示二叉树时,元素代表节点值,索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。
给定索引 𝑖 ,其左子节点的索引为 2𝑖+1 ,右子节点的索引为 2𝑖+2 ,父节点的索引为 (𝑖−1)/2(向下整除)。当索引越界时,表示空节点或节点不存在。
/* 获取左子节点的索引 */
int left(MaxHeap *maxHeap, int i) {
return 2 * i + 1;
}
/* 获取右子节点的索引 */
int right(MaxHeap *maxHeap, int i) {
return 2 * i + 2;
}
/* 获取父节点的索引 */
int parent(MaxHeap *maxHeap, int i) {
return (i - 1) / 2; // 向下取整
}
2. 访问堆顶元素
首个元素
3. 元素入堆
比较堆节点的val大小,以找到相应位置:堆化——修复从插入节点到根节点的路径上的各个节点
考虑从入堆节点开始,从底至顶执行堆化
/* 元素入堆 */
void push(MaxHeap *maxHeap, int val) {
// 默认情况下,不应该添加这么多节点
if (maxHeap->size == MAX_SIZE) {
printf("heap is full!");
return;
}
// 添加节点
maxHeap->data[maxHeap->size] = val;
maxHeap->size++;
// 从底至顶堆化
siftUp(maxHeap, maxHeap->size - 1);
}
/* 从节点 i 开始,从底至顶堆化 */
void siftUp(MaxHeap *maxHeap, int i) {
while (true) {
// 获取节点 i 的父节点
int p = parent(maxHeap, i);
// 当“越过根节点”或“节点无须修复”时,结束堆化
if (p < 0 || maxHeap->data[i] <= maxHeap->data[p]) {
break;
}
// 交换两节点
swap(maxHeap, i, p);
// 循环向上堆化
i = p;
}
}
4. 堆顶元素出堆
- 交换堆顶与堆底元素
- 删除交换后的堆底元素
- 从根节点开始,从顶至底堆化
/* 元素出堆 */
int pop(MaxHeap *maxHeap) {
// 判空处理
if (isEmpty(maxHeap)) {
printf("heap is empty!");
return INT_MAX;
}
// 交换根节点与最右叶节点(交换首元素与尾元素)
swap(maxHeap, 0, size(maxHeap) - 1);
// 删除节点
int val = maxHeap->data[maxHeap->size - 1];
maxHeap->size--;
// 从顶至底堆化
siftDown(maxHeap, 0);
// 返回堆顶元素
return val;
}
/* 从节点 i 开始,从顶至底堆化 */
void siftDown(MaxHeap *maxHeap, int i) {
while (true) {
// 判断节点 i, l, r 中值最大的节点,记为 max
int l = left(maxHeap, i);
int r = right(maxHeap, i);
int max = i;
if (l < size(maxHeap) && maxHeap->data[l] > maxHeap->data[max]) {
max = l;
}
if (r < size(maxHeap) && maxHeap->data[r] > maxHeap->data[max]) {
max = r;
}
// 若节点 i 最大或索引 l, r 越界,则无须继续堆化,跳出
if (max == i) {
break;
}
// 交换两节点
swap(maxHeap, i, max);
// 循环向下堆化
i = max;
}
}