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

堆的实现以及利用堆进行排序

news 来源：原创 2025/8/15 18:29:41

堆

堆的实现
- 1. 什么是堆？
- 2. 最小堆的核心操作
- - 2.1 初始化堆
  - 2.2 销毁堆
  - 2.3 插入元素
  - 2.4 删除堆顶元素
  - 2.5 获取堆顶元素
  - 2.6 判断堆是否为空
- 3. 调整堆的算法
- - 3.1 向上调整
  - 3.2 向下调整
- 4. 测试代码
堆排序
- - 一.向下调整建堆
  - 二.向上调整建堆
- 时间复杂度分析
- - 向上建堆分析：
  - 向下建堆分析
总结

堆的实现

在数据结构中，堆是一种非常重要的结构，尤其在需要频繁访问最大值或最小值的场景中。今天，我们将通过C语言实现一个最小堆，并详细介绍其核心功能和实现细节。最大堆的实现只需通过改变向上向下调整的大于小于号即可

1. 什么是堆？

堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最小堆中，父节点的值总是小于或等于其子节点的值。这种特性使得堆的根节点始终是所有节点中的最小值，非常适合实现优先队列。
在这里插入图片描述
堆有以下的性质：

堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
堆总是⼀棵完全⼆叉树。

⼆叉树性质

对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：
若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦
若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

2. 最小堆的核心操作

最小堆的基本操作包括初始化、插入、删除、获取堆顶元素、判断堆是否为空等。以下是这些操作的具体实现：

2.1 初始化堆

初始化堆时，我们需要为堆分配一个动态数组，并设置其容量和大小。

void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

2.2 销毁堆

销毁堆时，需要释放动态分配的内存，并将堆的指针和容量、大小重置为初始状态。

void HeapDestroy(Heap* hp)
{if (!hp) return;if (hp->a)free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;
}

2.3 插入元素

插入元素时，首先检查堆的容量是否已满。如果已满，则动态扩展容量。插入后，通过向上调整（AdjustUp）确保堆的性质。

int HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL)return -1;php->a = tmp;}php->a[php->size] = x;AdjustUp(php->a, php->size);php->size++;return 0;
}

2.4 删除堆顶元素

删除堆顶元素时，将堆顶元素与最后一个元素交换，然后减少堆的大小，并通过向下调整（AdjustDown）确保堆的性质。

void HeapPop(Heap* hp)
{assert(!HeapEmpty(hp));Swap(&hp->a[0], &hp->a[hp->size - 1]);hp->size--;AdjustDown(hp->a, 0, hp->size);
}

2.5 获取堆顶元素

堆顶元素即为堆的根节点，可以直接返回。

HPDataType HeapTop(Heap* hp)
{assert(hp);return hp->a[0];
}

2.6 判断堆是否为空

通过检查堆的大小是否为零来判断堆是否为空。

bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}

3. 调整堆的算法

堆的调整是实现堆操作的核心。向上调整（AdjustUp）和向下调整（AdjustDown）分别用于插入和删除操作。

3.1 向上调整

向上调整算法

• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后

• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
向上调整用于插入操作。从插入的节点开始，逐层向上比较和交换，直到满足堆的性质。

void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

3.2 向下调整

向下调整算法

• 将堆顶元素与堆中最后⼀个元素进⾏交换

• 删除堆中最后⼀个元素

• 将堆顶元素向下调整到满⾜堆特性为⽌

向下调整用于删除操作。从根节点开始，逐层向下比较和交换，直到满足堆的性质。

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child] > arr[child + 1])child++;if (arr[parent] > arr[child]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

4. 测试代码

以下是测试代码，用于验证堆的功能：

int main()
{Heap hp;HeapInit(&hp);HeapPush(&hp, 5);HeapPush(&hp, 3);HeapPush(&hp, 8);HeapPush(&hp, 2);printf("HeapTop: %d\n", HeapTop(&hp)); // 输出 2printf("HeapSize: %d\n", HeapSize(&hp)); // 输出 4HeapPop(&hp);printf("HeapTop after pop: %d\n", HeapTop(&hp)); // 输出 3HeapDestroy(&hp);return 0;
}

堆排序

堆排序时通常排的是升序，需改变adjust down的大于小于号，使其排最大堆；

一.向下调整建堆

构建最大堆：
初始时，数组是无序的，需要将其构建成一个最小堆。
从最后一个非叶子节点开始（索引为 (n - 1 - 1) / 2），逐个向上调整，确保每个子树都满足最大堆的性质。
调整完成后，数组的前半部分形成了一个最小堆。
排序过程：
每次将堆顶元素（最大值）与堆的最后一个元素交换，这样最大值就放到了数组的末尾。
然后缩小堆的范围（end–），并重新调整堆，确保剩余部分仍然是一个最小堆。
重复上述过程，直到堆中只剩下一个元素，此时数组已经完全排序

void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, 0, end);end--;}
}

二.向上调整建堆

（一）向上调整（AdjustUp）
向上调整是用于在插入新元素时，将元素调整到合适的位置，以保持堆的性质。其步骤如下：
比较当前节点与其父节点的值。
如果当前节点的值大于父节点的值（最大堆），则交换它们的位置。
更新当前节点为父节点，重复上述步骤，直到当前节点的值小于父节点的值，或者当前节点已经是根节点。
（二）向下调整（AdjustDown）
向下调整是用于在删除堆顶元素后，将堆重新调整为最大堆。其步骤如下：
比较当前节点与其子节点的值。
如果子节点的值大于当前节点的值（最大堆），则交换它们的位置。
更新当前节点为子节点，重复上述步骤，直到当前节点的值大于其子节点的值，或者当前节点已经是叶子节点。
（三）堆排序的完整过程
构建最大堆：从最后一个非叶子节点开始，逐个向上调整，直到根节点。

排序：

交换堆顶元素和最后一个元素。
对剩余的堆重新调整，使其满足最大堆的性质。
重复上述步骤，直到堆的大小为1。

void HeapSort1(int* a, int n) {// 构建最大堆for (int i = 0; i < n; i++) {AdjustUp(a, i);}//排序过程int end = n - 1;while (end > 0) {Swap(&a[0], &a[end]); // 交换堆顶和最后一个元素AdjustDown(a, 0, end); // 重新调整堆end--;}
}

在日常使用堆排序时，一般使用向下建堆，因为在考虑时间复杂度时，向下建堆要小于向上建堆。
在这里插入图片描述

时间复杂度分析

向上建堆分析：

第1层，0个结点，需要向上移动0层
第2层，2个结点，需要向上移动1层
第3层，4个结点，需要向上移动2层
第4层，8个结点，需要向上移动3层
…
第h层，2的h次个结点，需要向上移动h-1层
在这里插入图片描述

向下建堆分析

分析：
第1层，0个结点，需要向下移动h-1层
第2层， 2个结点，需要向下移动h-2层
第3层， 4个结点，需要向下移动h-3层
第4层，8个结点，需要向下移动h-4层
…
第h-1层，2 个结点，需要向下移动1层
到这里为止，就可以大略的看出其实向下建堆时间复炸度其实是要小的。
下面给出数学分析：
在这里插入图片描述

总结

通过上述代码，我们实现了一个功能完整的最小堆。堆的核心操作包括初始化、插入、删除、获取堆顶元素等。通过向上调整和向下调整算法，我们确保了堆的性质始终得以维护。

堆