当前位置：首页 > article >正文

堆的相关要点以及模拟实现

article 2025/3/26 14:42:07

定义

堆（Heap）是一种特殊的完全二叉树结构，它满足以下性质：

结构性：必须是完全二叉树

有序性：任意节点的值都满足特定的大小关系

大根堆：父节点值 ≥ 子节点值

小根堆：父节点值 ≤ 子节点值

完全二叉树的概念

定义：除了最后一层外，其他层的节点都是满的，且最后一层的节点都靠左排列

特点：

从上到下，从左到右依次填充

如果最后一层不满，缺少的部分一定在右边

性质

1. 结构性质

节点编号：从上到下，从左到右，从0开始编号

父子关系：对于任意节点 i

父节点索引 = (i - 1) / 2
左子节点索引 = 2 * i + 1
右子节点索引 = 2 * i + 2

深度关系：

n个节点的堆的高度为⌊log₂n⌋ + 1

第k层最多有2^(k-1)个节点

2.基本性质

堆的大小：n个节点的完全二叉树的高度为⌊log₂n⌋ + 1

节点位置：

最后一个非叶子节点的位置：n/2 - 1

第一个叶子节点的位置：n/2

查找性质：

查找最大值（大根堆）：O(1)
查找最小值（小根堆）：O(1)

模拟实现

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

具体实现

1.初始化和销毁

void HeapInit(Heap* hp)
{
assert(hp);
hp->_a = NULL;
hp->_capacity = 0;
hp->_size = 0;
}

void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->_a);
hp->_a = NULL;
hp->_capacity = 0;
hp->_size = 0;

}

堆的创建需要从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，这里需要掌握向上调整算法的应用

2.向上调整

// 交换两个元素
static void Swap(HPDataType* a, HPDataType* b) {
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}

// 向上调整（大堆）
static void AdjustUp(HPDataType* a, int child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] > a[parent]) { // 子节点大于父节点则交换
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break; // 满足堆条件，退出
}
}
}

3.插入

堆的插堆的尾部开始插入的，再进行向上调整算法，直到满足堆。

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
// 容量不足时扩容
if (hp->_size == hp->_capacity) {
int newCapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL) {
perror("realloc failed");
exit(-1);
}
hp->_a = tmp;
hp->_capacity = newCapacity;
}
hp->_a[hp->_size++] = x;
AdjustUp(hp->_a, hp->_size - 1);

}

如图所示，插入后向上的调整过程：

4.向下调整

删除堆是删除堆顶的数据，将堆顶的数据和最后一个数据交换，然后删除数组最后一个数据，再进行向下调整

// 向下调整（大堆）
static void AdjustDown(HPDataType* a, int size, int parent) {

int child = parent * 2 + 1; // 左子节点
while (child < size) {
// 选出较大的子节点
if (child + 1 < size && a[child + 1] > a[child])
{
child++;
}

if (a[child] > a[parent])
{
// 子节点大于父节点则交换
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break; // 满足堆条件，退出
}
}
}

5.删除

删除堆顶元素

// 堆的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->_size);

Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
AdjustDown(hp->_a, hp->_size, 0);

}

//调整过程如图所示

6.其余操作

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp && hp->_size > 0);
return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;

}
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
return hp->_size == 0;
}