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