9、取堆顶数据
若堆非空，则取0下标位置数据：
HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; }
10、计算堆大小
这就更简单了，直接返回 size：
int HeapSize(HP* php) { assert(php); return php->size; }
11、判空
只要 size == 0 ，堆就为空：
bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
12、打印堆
void HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); }
四、完整代码
Heap.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; // 堆的构建 void HeapCreate(HP* hp, HPDataType* a, int n); void HeapPrint(HP* php); void HeapInit(HP* php); void HeapDestroy(HP* php); // 保持他继续是一个堆 O(logN) void HeapPush(HP* php, HPDataType x); // 删除堆顶的数据，并且保持他继续是一个堆 O(logN) void HeapPop(HP* php); HPDataType HeapTop(HP* php); int HeapSize(HP* hp); // 堆的判空 bool HeapEmpty(HP* hp);
Heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" void HeapPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); } // 初始化 不开空间 void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; } // 销毁 void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; } void Swap(HPDataType* p1, HPDataType* p2) { assert(p1 && p2); HPDataType tmp = *p1; *p1 = *p2; *p2 = tmp; } // 向上调整 void AdjustUp(HPDataType* a, int child) { assert(a); // 算父亲 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; } } } // 保持他继续是一个堆 O(logN) void HeapPush(HP* php, HPDataType x) { assert(php); // 检查容量 if (php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } // 插入元素 php->a[php->size++] = x; // 向上调整 AdjustUp(php->a, php->size - 1); } // 向下调整 void AdjustDown(HPDataType* a, int n, int parent) { // 假设最小孩子 int minchild = 2 * parent + 1; while (minchild < n) { // 找最小孩子 if (minchild + 1 < n && a[minchild + 1] < a[minchild]) { minchild++; } if (a[parent] > a[minchild]) { Swap(&a[parent], &a[minchild]); parent = minchild; minchild = 2 * parent + 1; } else { break; } } } // 删除堆顶的数据，并且保持他继续是一个堆 O(logN) void HeapPop(HP* php) { assert(php); assert(php->size > 0); // 交换堆顶和最后一个节点的值 Swap(&php->a[0], &php->a[php->size - 1]); // 尾删 php->size--; AdjustDown(php->a, php->size, 0); } HPDataType HeapTop(HP* php) { assert(php); assert(php->size > 0); return php->a[0]; } int HeapSize(HP* php) { assert(php); return php->size; } // 堆的判空 bool HeapEmpty(HP* php) { assert(php); return php->size == 0; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Heap.h" void TestHp1() { HP hp; HeapInit(&hp); int arr[] = { 27,15,19,18,28,34,65,49,25,37 }; int sz = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < sz; i++) { HeapPush(&hp, arr[i]); } HeapPrint(&hp); HeapPop(&hp); HeapPrint(&hp); // 取五个最小数据 /*int k = 5; while (k--) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); }*/ HeapDestroy(&hp); } void TestHp2() { int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(array) / sizeof(int); ++i) { HeapPush(&hp, array[i]); } // 排序 while (!HeapEmpty(&hp)) { printf("%d ", HeapTop(&hp)); HeapPop(&hp); } HeapDestroy(&hp); } int main() { TestHp1(); //TestHp2(); return 0; }
到这里，本篇博客就到此结束了。看到这儿，相信大家也对堆有了一定的了解。
今天的内容在二叉树一块还是较简单的。下篇博客我会讲解由堆引申出的两个堆的应用 —— 堆排序 和 TopK问题。所以今天的内容还是很重要的，只有看懂下篇博客理解起来才比较清晰。
如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！
我是anduin，一名C语言初学者，我们下期见！
