数据结构之堆(topk问题、堆排序)
数据结构之堆(topk问题、堆排序)
一、堆的初步认识
堆虽然是用数组存储数据的数据结构，但是它的底层却是另一种表现形式。
堆分为大堆和小堆，大堆是所有父亲大于孩子，小堆是所有孩子大于父亲。
通过分析我们能得出父子关系的计算公式，parent=(child-1)/2，左孩子leftchild=parent*2+1，右孩子rightchild=parent*2+2，这会在下面实现时应用。
二、堆实现
1、头文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapPrint(HP* php);//堆打印
void HeapInit(HP* php);//堆初始化
void HeapPush(HP* php, HPDataType x);//堆插入
void HeapPop(HP* php);//堆删除
HPDataType HeapTop(HP* php);//返回堆顶元素
bool HeapEmpty(HP* php);//判空
int HeapSize(HP* php);//返回堆大小
void AdjustUp(HPDataType* a, int child);//向上调整
void AdjustDown(HPDataType* a, int n, int parent);//向下调整
void Swap(HPDataType* x, HPDataType* y);//交换函数
void HeapSort(int* arr, int n);//堆排序
void HeadDestroy(HP* php);//堆销毁这里用结构体管理数据，HPDataType*a是动态数组的指针，HPDataType是typedef定义的可变参数，需要更改存储类型时，修改typedef的内容即可，size用于统计存储数据的多少，capacity是统计开辟的空间大小，即动态申请数组的大小。
2、 堆初始化
void HeapInit(HP* php)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)* 4);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
php->size = 0;
php->capacity = 4;
}assert检查指针是否为空，malloc动态申请空间，然后对size和capacity(空间的大小)初始化
3、堆打印
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}4、向上调整
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
/*while (a[parent] < a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
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;
}
}向上调整用于解决插入数据造成的不构成堆的问题
5、堆插入
当我们插入一个值时，这个新插入的值也许会破坏原本的堆关系，所以我们需要进行向上调整，使其恢复堆关系。
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* php->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;//size代表元素个数，a[size]为下一个元素
php->size++;
AdjustUp(php->a, php->size - 1);//向上调整
}6、向下调整
void AdjustDown(HPDataType* a,int n ,int parent)
{
/*int child = a[parent * 2 + 1] > a[parent * 2 + 2] ? parent * 2 + 1 : parent * 2 + 2;
while (child < n)
{
Swap(&a[parent], &a[child]);
parent = child;
child = a[parent * 2 + 1] > a[parent * 2 + 2] ? parent * 2 + 1 : parent * 2 + 2;
}*/
int child = parent * 2 + 1;//左孩子
while (child < n)
{
//选出左右孩子中大的那一个
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child]>a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}7、堆删除
这里选择堆顶元素和堆底元素交换，如果挪动数据会导致父子关系乱套，而这里不free最后一个元素，避免释放后继续使用。
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
//挪动删除:1.效率低下2.关系全乱
//只需要交换第一个元素和最后一个元素值，并php->size--
//1.效率高2.保持父子关系
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}8、返回堆顶元素
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}动态数组中存储的第一个元素就是堆顶元素
9、堆判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}通过size的数量判空，如果为0，则堆为空，返回true
10、堆大小
int HeapSize(HP* php)
{
assert(php);
return php->size;
}这里结构体中有size数据，返回即可。
11、堆销毁
void HeadDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}free掉a指针指向的空间，a指针置空，size和capacity赋值0.
三、扩展
1、堆排序(升序大堆，降序小堆)
时间复杂度O(N*logN)
先对要排序的数组建堆，然后交换堆顶元素，对剩余的元素向下调整。
void HeapSort(int* arr, int n)
{
for (int i = (n-2)/2; i >0; i--)
{
AdjustDown(arr, n, i);
}
int end = n - 1;
while (end)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
}2、topk问题
用k个元素建小堆，剩余n-k个元素与堆顶元素比较交换即可，最后k大小的小堆中保留的是这n个数中前k个最大的数。
看到最后，如果对您有所帮助，请点赞、收藏和关注，点点关注不迷路，源码已上传Gitee有需自取：白天没有黑夜 (not-during-the-day) - Gitee.com，我们下期再见！
腾讯云开发者
