数据结构之堆(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，我们下期再见！