文章目录
- 前言
一、堆（顺序结构）头文件Heap.h
二、堆（顺序结构）各接口具体实现Heap.c
- 2.1 初始化堆
- 2.2 销毁堆
- 2.3 交换结点
- 2.4 向上调整新堆
- 2.5 堆的插入
- 2.6 向下调整新堆
- 2.7 删除堆顶数据（最小/最大）
- 2.8 打印堆
- 2.9 堆的判空
- 2.10 堆的数据个数
- 2.11 取堆顶的数据
- 2.12 堆排序
- 2.13 优化堆排序
- 2.14 TOP-K问题
三、堆（顺序结构）接口测试test.c
- 总结
前言
本文总结学习堆（顺序结构）的各个接口C语言实现。
一、堆（顺序结构）头文件Heap.h
本节主要包含：结构体类型创建，函数声明，头文件包含
#pragma once
#include 二、堆（顺序结构）各接口具体实现Heap.c
本节主要包含：各个接口的实现方法
2.1 初始化堆// 初始化堆
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
// 也有一种初始化方式(开辟出空间，直接将数组内容拷贝到它的空间去，然后使用建堆算法)
// void HeapInitArray(HP* php, HPDataType* a, size_t n)
// 销毁堆
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
// 交换结点
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
// 向上调整新堆
void AdjustUp(HPDataType* a, size_t child)
{
// 算法逻辑思想是二叉树，物理上 *** 作的是数组中的数据
while (child > 0)
{
// 记录该轮循环的父结点，并起到更新父结点的作用
size_t parent = (child - 1) / 2;
if (a[child] > a[parent]) // 此处为大堆
{
// 交换父子结点
Swap(&a[child], &a[parent]); // 注！！！！！！！传地址可能真正交换
// 向上更新子结点
child = parent;
}
else
{
// 一旦不再满足子结点大于父结点就退出循环，该数据结构已经形成堆
break;
}
}
}
// 堆的插入（尾部插入，效率最高，影响面最小，插入后依旧保持为（大/小）堆，时间复杂度o(h)->o(logN)）
void HeapPush(HP* php, HPDataType x)
{
assert(php);
// 判断是否满（因为HeapInit将结构体成员都置为空或0，所以这里的判断包括初始为空的情况）
if (php->capacity == php->size)
{
size_t newCapacity = (0 == php->capacity) ? 4 : (2 * (php->capacity));
// 注！！！！！！！！！扩容应该用realloc而不是malloc，因为扩容需保存之前空间的数据
HPDataType* tmp = (HPDataType*)realloc(php->a ,newCapacity * sizeof(HPDataType));
if (NULL == tmp)
{
printf("malloc fail\n");
exit(-1);
}
else
{
php->a = tmp;
php->capacity = newCapacity;// 注！！！！！！！！赋值给新容量
}
}
(php->a)[(php->size)++] = x;
// 向上调整算法（插入数据后，可能不再为堆）
// 比较该结点和其父结点，如果该结点的值大于其父结点，交换二者，更新父子结点，再次比较，直到子结点更新为根结点
AdjustUp(php->a, (php->size) - 1);
}
// 向下调整新堆
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
// 找到较大孩子（此处为大堆）
// 1-先默认赋值较大孩子为左孩子 ！！！！！！！！！！！！循环条件为判断子结点
size_t child = parent * 2 + 1;
while (child < size) // 当左孩子已经存在时进入循环
{
// 2-如果右孩子存在且大于左孩子，则将较大孩子选为右孩子 ！！！！！！！！
// 注：(child + 1) < 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;
}
}
}
// 删除堆顶数据（最小/最大）
void HeapPop(HP* php)
{
assert(php);
// 挪动数据覆盖根位置的数据删除
// 1-挪动数据时间复杂度O（n）
// 2-堆结构破坏了，父子间的关系全部乱了
// 正确方法：
// 1-第一个数据（根位置）和最后一个位置进行交换o(1)
// 2-删除最后一个数据o(1)
// 3-向下调整o(h)->o(log N)
assert(php->size > 0); // 注！！！！！！！！！！防止(php->size)--出问题
// 交换
Swap(&((php->a)[0]), &((php->a)[php->size - 1]));
// 删除原堆顶数据
(php->size)--;
// 向下调整
// 1-先对比该父结点的两个子结点，找到较大（此处为大堆）的，与父结点交换
// 2-向下更新父子结点，直到子结点下标大于size
AdjustDown(php->a, php->size, 0);
}
// 打印堆
void HeapPrint(HP* php)
{
assert(php);
int i = 0;
for (i = 0; i < (php->size); i++)
{
printf("%d ", (php->a)[i]);
}
printf("\n");
}
// 堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return 0 == (php->size);
}
// 堆的数据个数
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0); // 当size为0时，获取下标0的数据是错误的
return (php->a)[0];
}
// 堆排序（升序建小堆）(时间复杂度o(n*logn)，空间复杂度o(n))
void HeapSort(int* a, int size)
{
HP hp = { 0 };
HeapInit(&hp);
// 时间复杂度o(n * log n)
int i = 0;
for (i = 0; i < size; i++)
{
HeapPush(&hp, a[i]);
}
// 时间复杂度o(n * log n)
int j = 0;
while (!HeapEmpty(&hp))
{
a[j++] = HeapTop(&hp);
HeapPop(&hp);
}
HeapDestroy(&hp);
}
// 优化堆排序（升序建大堆，降序建小堆）(时间复杂度o(n*logn)，空间复杂度o(1))
void HeapSortplus(int* a, int size)
{
// 向上调整建堆
// 根结点无需向上调整（向上调整传入子结点下标），所以从根结点下一个结点向上调整建堆
for (int i = 1; i < size; i++)
{
AdjustUp(a, i);
}
// 向下调整建堆
// 叶子结点无需向下调整（向上调整传入父结点下标），所以从最后一个非叶子结点（最后一个结点的父亲）开始向下调整建堆，
// 依次下标减一就到下一个局部父结点位置
/*for (int j = ((size - 1) - 1) / 2; j >= 0; j--)
{
AdjustDown(a, size, j);
}*/
// 升序，建大堆（降序建小堆） 时间复杂度o(n * logn)
for (int i = size - 1; i > 0; i--)
{
// 将堆顶元素（最大值）交换至最后
Swap(&a[i], &a[0]);
// 有效下标减一，锁定升序数组最后的最大值，将它放在堆外
size--;
// 重新向下调整，构建新的大堆，重复上述
AdjustDown(a, size, 0);
}
}
见test.c
三、堆（顺序结构）接口测试test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
// TOPK
void PrintTopK(int* a, int n, int k)
{
// 假设选出数据前K个最大的元素
// 1. 建堆:用a中前k个元素建堆
// （建小堆）
// 开辟该数据结构的空间
int* kminheap = (int*)malloc(k * sizeof(int));
assert(kminheap);
// 赋值前k个元素给该数据结构
for (int i = 0; i < k; i++)
{
kminheap[i] = a[i];
}
// 向上调整该数据结构顺序建立小堆（也可以向下调整建堆）
for (int i = 1; i < k; i++)
{
AdjustUp(kminheap, i);
}
// 2. 将剩余n-k个元素中大于堆顶元素的，依次与堆顶元素交换，将更大的数据换入堆内
for (int i = k; i < n; i++)
{
if (kminheap[0] < a[i])
{
kminheap[0] = a[i];
AdjustDown(kminheap, k, 0);
}
}
// 3.打印
for (int i = 0; i < k; i++)
{
printf("%d ", kminheap[i]);
}
printf("\n");
free(kminheap);
kminheap = NULL;
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2335] = 1000000 + 6;
a[9999] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
PrintTopK(a, n, 10);
}
int main()
{
// 堆的初始状态为一个结构体
HP hp = { 0 };
// 初始化堆
HeapInit(&hp);
// 堆的插入
HeapPush(&hp, 9);
HeapPush(&hp, 8);
HeapPush(&hp, 7);
HeapPush(&hp, 6);
HeapPush(&hp, 5);
HeapPush(&hp, 4);
HeapPush(&hp, 8);
// 打印堆
HeapPrint(&hp);
// 删除堆顶数据（最小/最大）
HeapPop(&hp);
// 打印堆
HeapPrint(&hp);
// 销毁堆
//HeapDestroy(&hp);
// 获取堆大小和堆顶数据
printf("%d %d\n", HeapSize(&hp), HeapTop(&hp));
// 堆排序测试：
int a[] = { 9, 2, 3, 1, 4 };
// 传统版：
//HeapSort(a, sizeof(a) / sizeof(a[0]));
// 优化版：
HeapSortplus(a, sizeof(a) / sizeof(a[0]));
int i = 0;
for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
printf("%d ", a[i]);
}
printf("\n");
// TOPK问题:
//TOP - K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
// 比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
// 对于Top - K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
// 数据都不能一下子全部加载到内存中)。
最佳的方式就是用堆来解决，基本思路如下：
// 1. 用数据集合中前K个元素来建堆
// 前k个最大的元素，则建小堆
// 前k个最小的元素，则建大堆
// 2. 用剩余的N - K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
// 将剩余N - K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
TestTopk();
return 0;
}
总结
这里对文章进行总结：
以上就是今天总结的内容，本文包括了C语言实现堆（顺序结构）各个接口，分享给大家。
真💙欢迎各位给予我更好的建议，欢迎访问！！！小编创作不易，觉得有用可以一键三连哦，感谢大家。
peace
希望大家一起坚持学习，共同进步。
梦想一旦被付诸行动，就会变得神圣。
欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）