【数据结构】堆的实现及TOP-K问题
?
?
前言
在正式讲堆之前，我们要先来讲一下二叉树的顺序结构：
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
?
?
1. 堆的概念及结构
如果有一个关键码的集合K = { k k k0， k k k1， k k k2，… ， k k kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： K K Ki <= K K K2*i+1 且 K K Ki <= K K K2*i+2（ K K Ki >= K K K2*i+1 且 K K Ki >= K K K2*i+2） i = 0，1，2，… ，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆的性质：
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一颗完全二叉树。
来看几道题：
1.下列关键字序列为堆的是：（）
A 100, 60, 70, 50, 32, 65
B 60, 70, 65, 50, 32, 100
C 65, 100, 70, 32, 50, 60
D 70, 65, 100, 32, 50, 60
E 32, 50, 100, 70, 65, 60
F 50, 100, 70, 65, 60, 32
2.已知小根堆为8, 15, 10, 21, 34, 16, 12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。
A 1
B 2
C 3
D 4
3.一组记录排序码为(5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为
A(11 5 7 2 3 17)
B(11 5 7 2 17 3)
C(17 11 7 2 3 5)
D(17 11 7 5 3 2)
E(17 7 11 3 5 2)
F(17 7 11 3 2 5)
4.最小堆[0, 3, 2, 5, 7, 4, 6, 8], 在删除堆顶元素0之后，其结果是（）
A[3，2，5，7，4，6，8]
B[2，3，5，7，4，6，8]
C[2，3，4，5，7，8，6]
D[2，3，4，5，6，7，8]
// 答案
1.A
2.C
3.C
4.C
?
?
2. 堆的实现
在讲堆的实现之前，我们要先来理解一下，堆是一个很讲究的数据结构，设计得是非常美妙的：
?
2.1 堆向上调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从最后一个孩子节点开始的向上调整算法可以把它调整成一个大堆。
讲了这些，我们用代码来实现一下这个过程：
// 向上调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustUp(HPDataType* a, int child, int (*compare)(const void*, const void*))
{
assert(a);
int parents = (child - 1) / 2; //找到孩子节点的父节点
while (child > 0)
{
if (compare(&a[parents], &a[child]) > 0) // 通过用户自己写的一个函数来判断是建大堆还是小堆
{
Swap(&a[child], &a[parents]);
// 调整孩子节点和父节点的位置
child = parents;
parents = (child - 1) / 2;
}
else
break;
}
}
这就是我们向上调整算法的实现，但相比较于向下调整算法，向上调整的效率还是比较低的，所以我们重点掌握向下调整算法就行了。
?
2.2 堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
我们用代码来实现一下这个逻辑：
// 向下调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustDown(HPDataType* a, int parents, int size, int (*compare)(const void*, const void*))
{
assert(a);
int child = parents * 2 + 1; // 先将左孩子设置为孩子节点
while (child < size)
{
// 这里我们以建大堆为例
if (child + 1 < size && compare(&a[child], &a[child + 1]) > 0)
{
// 比较左孩子和右孩子,如果右孩子比左孩子大,就将孩子节点++
child++;
}
if (compare(&a[parents], &a[child]) > 0) // 如果父亲节点小于孩子节点,就进行交换
{
Swap(&a[parents], &a[child]);
// 调整孩子节点和父节点的位置
parents = child;
child = parents * 2 + 1;
}
else
break;
}
}
?
2.3 堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = { 1,5,3,8,7,6 };
?
2.4 堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
?
2.5 堆的常用接口代码实现
// 交换
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustUp(HPDataType* a, int child, int (*compare)(const void*, const void*))
{
assert(a);
int parents = (child - 1) / 2; //找到孩子节点的父节点
while (child > 0)
{
if (compare(&a[parents], &a[child]) > 0) // 通过用户自己写的一个函数来判断是建大堆还是小堆
{
Swap(&a[child], &a[parents]);
// 调整孩子节点和父节点的位置
child = parents;
parents = (child - 1) / 2;
}
else
break;
}
}
// 向下调整
// 这里我用了一个函数指针,目的是方便我们自己可以选择建大堆还是建小堆,如果不理解这个代码也没事,
// 我们在建大堆或者小堆的时候就需要手动去调整代码
void AdjustDown(HPDataType* a, int parents, int size, int (*compare)(const void*, const void*))
{
assert(a);
int child = parents * 2 + 1; // 先将左孩子设置为孩子节点
while (child < size)
{
// 这里我们以建大堆为例
if (child + 1 < size && compare(&a[child], &a[child + 1]) > 0)
{
// 比较左孩子和右孩子,如果右孩子比左孩子大,就将孩子节点++
child++;
}
if (compare(&a[parents], &a[child]) > 0) // 如果父亲节点小于孩子节点,就进行交换
{
Swap(&a[parents], &a[child]);
// 调整孩子节点和父节点的位置
parents = child;
child = parents * 2 + 1;
}
else
break;
}
}
// 堆的构建
void HeapCreate(Heap* hp)
{
assert(hp);
hp->_a = NULL;
hp->_size = hp->_capacity = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->_a);
hp->_size = hp->_capacity = 0;
}
// 堆的打印
void HeapPrint(Heap* hp)
{
assert(hp);
int i = 0;
for (i = 0;i < hp->_size;i++)
{
printf("%d ", hp->_a[i]);
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x, int (*compare)(const void*, const void*))
{
assert(hp);
//扩容
if (hp->_size == hp->_capacity)
{
int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
hp->_a = tmp;
hp->_capacity = newcapacity;
}
// 插入
hp->_a[hp->_size] = x;
// 向上调整
AdjustUp(hp->_a, hp->_size, compare);
hp->_size++;
}
// 堆的删除
void HeapPop(Heap* hp, int (*compare)(const void*, const void*))
{
assert(hp);
assert(hp->_a);
assert(hp->_size >= 0);
Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
// 向下调整
AdjustDown(hp->_a, 0, hp->_size, compare);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
return hp->_size == 0;
}
?
?
3. 堆的应用
TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top - K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
-
用数据集合中前K个元素来建堆
- 前K个最大的元素，则建小堆
- 前K个最小的元素，则建大堆
-
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
我们先写一个程序来创建一亿个数的程序，然后我在创建出来的文件中，随机修改了十个数，把他们改得都很大，因为我也不知道我是在哪些地方改的所以就不展示了：
void CreateNDate()
{
int num = 100000000;
int i = 0;
FILE* pf = fopen("data.txt", "w");
if (pf == NULL)
{
perror("fopen");
exit(-1);
}
for (i = 0;i < num;i++)
{
fprintf(pf, "%d\n", rand() % 100000000);
}
fclose(pf);
}
int main()
{
//创建一个含有一亿个数字的文件
srand((unsigned int)time(NULL));
CreateNDate();
return 0;
}
接下来我们就来试试吧：
//建堆时,根据该函数来决定大堆还是小堆
int CreakSmallHeap(const void* x, const void* y)
{
return *(int*)x - *(int*)y;
}
void PrintTopK(int k)
{
// 定义一个堆结构来存放数据
Heap hp;
// 堆的大小取决于我们要找的前k个数
hp._a = (HPDataType*)malloc(sizeof(HPDataType) * k);
if (hp._a == NULL)
{
perror("malloc fail");
exit(-1);
}
hp._capacity = k;
hp._size = 0;
//打开文件
FILE* pf = fopen("data.txt", "r");
if (pf == NULL)
{
perror("fopen fail");
exit(-1);
}
//用前k个数建堆
int i = 0;
for (i = 0;i < k;i++)
{
int a = 0;
fscanf(pf, "%d", &a);
HeapPush(&hp, a, CreakSmallHeap);
}
//遍历文件,比堆头大的数就进堆,并向下调整
while (fscanf(pf, "%d", &i) != EOF)
{
if (i > hp._a[0])
{
hp._a[0] = i;
AdjusutDown(hp._a, 0, k, CreakSmallHeap);
}
}
for (i = 0;i < k;i++)
{
printf("%d ", hp._a[i]);
}
printf("\n");
//销毁栈
HeapDestory(&hp);
//关闭文件
fclose(pf);
}
int main()
{
创建一个含有一亿个数字的文件
//srand((unsigned int)time(NULL));
//CreateNDate();
PrintTopK(10);
return 0;
}
结果如下：
还有一个问题：
可能有人不知道为什么我们找最大的前几个数为什么要建小堆，难道不能建大堆，然后将后面取到的数与堆的最后一个数比较吗？原因是：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！