堆和堆排序【数据结构】

前言:
什么是堆呢？
堆（Heap）是一种数据结构，它是 一种特殊的二叉树 ，其中父节点的键值总是大于或等于（或小于或等于）其任何一个子节点的键值。这意味着在堆中，根节点具有最大（或最小）键值。
堆：一般是数组数据看做一棵完全二叉树
完全二叉树的逻辑结构：

• 大堆： 任意一个父结点 大于等于 子结点
  

• 小堆： 任意一个父结点 小于等于 子结点
  
  数组存储完全二叉树
  

一、堆

1. 堆的存储定义

因为存储结构，这里使用动态数组的形式来存放数据。但是也要注意其中的逻辑结构是完全二叉树。定义一个指针指向动态数组，定义存储堆的容量capacity，记录堆中的数据的个数size

代码

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;	//指向动态数组int capacity;	//堆的容量int size;		//堆中数据个数
}Heap;

2. 初始化堆

类似顺序表的初始化

代码

//初始化堆
void InitHeap(Heap* hp) 
{assert(hp);hp->a = NULL;hp->capacity = 0;hp->size = 0;
}

3. 销毁堆

避免内存泄漏

代码

//销毁堆
void DestroyHeap(Heap* hp) 
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;	
}

4. 堆的插入

重点：
在堆的插入前，我们需要注意的就是，首先判断其容量，然后使用realloc给数组分配空间
分配空间后，把数据插入堆。但是数据在插入堆时，由于堆一般分为大根堆和小根堆，所以这里使用的大根堆。 大堆：父结点的值大于等于其孩子结点的值
但是数据的值不能确定，这个时候就需要我们使用 堆的向上调整算法

向上调整算法

在数组的末端插入元素，进行与其父结点进行比较，大堆的情况下，如果其孩子结点的值大于父亲结点的值时，把插入的数据向上调整，向上调整的方法是:把插入的数据与其父结点进行交换，交换后继续判断是否还需要向上调整。(使用向上调整算法的条件是前面结点的树是构成堆的)

这里是使用的是数组，所以当插入元素时，在数组的末端进行插入数据

物理存储：

逻辑存储情况：

在插入的数据时，我们就需要考虑一下，
1. 当插入的孩子结点的值大于其父亲结点的值时，就向上调整
思路：
首先是根据孩子结的下标找父结点的下标，（孩子结点下标-1）/2 == 父结点下标，因为可能调整所以将判断条件放到循环里面(当然也可以用递归)，在循环里面切记一定要及时更新当前孩子结点的下标和父结点的下标，孩子结点的值大于父结点的值就向上调整，否则就跳出循环。当孩子结点的下标到0时，向上调整完成，循环结束。

2. 当小于等于时，不需要调整

代码

//向上调整
void AdjustUp(HPDataType * a,int child) 
{//先找到父结点的下标int parent = (child - 1) / 2;while (child > 0)	//child等于0时，说明已经调整ok了{if (a[child] > a[parent]){swap(&a[child], &a[parent]);//可能会向上调整多次child = parent;parent = (parent - 1) / 2;}else {break;}}
}//堆的插入
void PushHeap(Heap* hp, HPDataType x)
{assert(hp);//堆满判断if (hp->capacity == hp->size) {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;hp->size++;//堆的向上调整AdjustUp(hp->a,hp->size-1);
}

调试，查看一下数据存储情况

5. 堆的删除

堆中元素的删除，发现直接删除尾结点是简单的(size减一即可)，但是，一般堆，删除元素都是删除的头结点。
直接删除头结点时：发现逻辑结构上变成了两棵树，这样直接删除头结点的方法不推荐。

交换结点再删除
头尾结点交换后，再删除尾结点，然后头结点使用堆的向下调整算法，调堆。
使用前提就是，当进行交换的时候，保证左右仍是堆。第一个结点与最后一个结点的值交换后，向下调整。

向下调整算法

这里调的堆是大堆（根结点的值大于左右孩子结点的值）

• 第一步，找到第一个根结点的孩子结点，这里使用假设法，先让左孩子的值最大，再进行判断左孩子还是右孩子的值是最大的，找出大的。
• 第二步与根结点进行比较，大于根结点就交换。
• 及时更新父结点和孩子结点的下标
• 注意当孩子结点值都小于父亲结点值就跳出循环;循环结束条件：孩子结点的下标大于数组最大的下标(就是孩子下标<数组的个数，child<size,大于等于时说明循环就结束了)。

过程：

调整后

这样就完成堆头结点的删除。
还需要注意的就是：

代码

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先去找根结点的较大的孩子结点int child = 2 * parent + 1;//可能会向下调整多次while (child<size) {//这里使用假设法，先假设左孩子的值最大//如果不对就进行更新if ((child+1 < size)&&a[child] < a[child+1]) {child++;}//根结点与其孩子结点中的较大的一个进行交换if(a[child] > a[parent]) {swap(&a[child],&a[parent]);//更新下标parent = child;child = 2 * parent + 1;}else {break; //调完堆}}
}
//堆的删除
void PopHeap(Heap* hp)
{assert(hp);assert(hp->size>0);//头尾交换swap(&hp->a[0],&hp->a[hp->size-1]);hp->size--;//向下调整AdjustDown(hp->a,hp->size,0);
}

调试一下：

上图中指向下标6其实有数据65的，但是数组的下标有效范围在0-5

6. 获取堆顶数据

前提:堆得有数据
代码

//获取堆顶数据
HPDataType TopHeap(Heap* hp) 
{assert(hp);assert(hp->size>0);return hp->a[0];
}

7. 获取堆的数据个数

代码

//获取堆的数据个数
int SizeHeap(Heap* hp)
{assert(hp);return hp->size;
}

8. 堆的判空

代码

//堆的判空
bool EmptyHeap(Heap* hp) 
{assert(hp);return hp->size == 0;
}

二、Gif演示

调堆演示

三、 堆排序

堆排序是一种选择排序。
堆排序：可以从小到大进行排序(使用大堆)。Top k 问题：取出最大的前k个值。

1. 堆排序

堆排序（Heap Sort）是一种基于完全二叉树的排序算法，它通过将待排序的元素建成一个二叉堆。堆排序的时间复杂度为O(nlogn)，它是不稳定排序算法。

堆排序的思路如下：

1. 以升序排序为例，先建立一个大堆（父节点的值大于子节点的值），将待排序的元素都插入堆中。
2. 将堆顶元素（最大值）与堆末尾元素交换，然后将堆的大小减1。
3. 对堆顶元素向下调整操作，使得堆重新满足最大堆的性质。
4. 重复2-3步，直到堆的大小为1。排序完成。

(1) 建大堆

使用 向下 调整算法来向上建堆：使用向下调整算法，把数组调成大堆
因为堆本身是一个完全二叉树，假设一共有h层，我们从第h-1层(即不是叶子结点的那一层开始)
因为是大堆，根结点的值大于孩子结点的值，从最下方使用向下调整来不断把较大的值来调到根节点。
注意：虽然使用的是向下调整算法，其实还是不断往上调整（把大的值调到上面）。
如图:

直到调整到第一层为止
建堆时间复杂度：O(N)

//堆排序
void HeapSort(int* arr, int n) 
{int i = 0;//使用向下调整算法向上调整，把大的值调到上方。for (i = (n - 1 - 1) / 2; i >= 0;i--){//先找到数组最后端的父结点的下标//父结点的下标减一就是另一个//使用向下调整算法进行调整AdjustDown(arr,n,i);}
}

当然也可以用向上算法进行向上建堆。

思路：先让一个独自成堆，然后尾插一个结点，再进行与根结点进行比较，大于根结点的值就交换。
但是这个使用向上调整算法向上建堆的时间复杂度为：O(Nlog(N))

//向上调整算法进行堆排序
void HeapSort(int* arr, int n)
{int i = 0;//先让第一个结点独自成堆//再一次尾增结点进行向上调整for (i = 1; i < n; i++) {AdjustUp(arr,i);}
}

(2) 排序

因为建成大堆后，将堆顶元素（最大值）与堆末尾元素交换

	//注意end 是从n-1开始的(数组最后一个元素的下标)int end = n-1;while (end > 0) {//swap end = n-1 这表示下标swap(&arr[0],&arr[end]);//adjustdown 函数里面的end是元素的个数，所以不是先--end//所以AdjustDown(arr,end,0);end--;}

注意这里的end–,上述是从数组最后一个元素下标n-1 开始。堆的首元素与尾元素交换完后，接着就是堆的个数减1，然后下进行向下调整。这里的end–放在了最后。因为AdjustDown中的第二个参数是传的是堆的大小，正好数组下标n-1 , 堆由n减一也是 n -1。

下方给出了 end 从n 开始的优化,但是可读性就会下降

void HeapSort(int* arr, int n)
{int i = 0;//先建成一个大堆for (i = (n - 1 - 1) / 2; i >= 0;--i) {AdjustDown(arr,n,i);}//堆顶元素与堆尾元素进行交换，进而把大的元素放到后面int end = n;while (end > 0) {swap(&arr[--end],&arr[0]);AdjustDown(arr,end,0);}
}

2.Topk问题

topk问题，例如：在10000个数据排名中找出前10；或者在10000个数中找出最大的前10个

这里我们就以在10000个数中找出最大的前10(k = 10)个为例

首先应先准备数据,随机生成10000个数(注意srand函数只能生成30000多个随机数)
核心思想： 建一个可以存储k个数据的小堆。先把文件数据前10个数据读取到小堆中(进行向下调成小堆)，然后再把文件中的其他数据一个一个读出与小堆的根结点的值进行比较，如果大于小堆的根结点，就进放入堆中，然后进行向下调堆。

//创建数据
void Createdata() 
{int n = 10000;srand((unsigned)time(0));const char* file = "data.txt";FILE* fin = fopen(file,"w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n;i++){int x = (rand() + i) % 100000;//把随机生成的数据写到fin文件中去fprintf(fin,"%d\n",x);}fclose(fin);
}

void PrintTopK(int k) 
{//从文件中读出数据const char* file = "data.txt";FILE* fout = fopen(file,"r");if (fout == NULL){perror("fout error");return;}//将数据读出到容量为k的动态数组中int* arr = (int*)malloc(sizeof(int)*k);if (arr == NULL){perror("malloc error");exit(-1);}//先把前k个数据放入数组中for (int i = 0; i < k; i++){//将数据读到数组中fscanf(fout,"%d",&arr[i]);//放数据的同时进行建堆AdjustUp(arr,i);}int x = 0;//当文件里面的数据读完后会返回EOFwhile (fscanf(fout, "%d", &x) != EOF) {//当从文件拿出的数据大于小堆中的数据时//将数据放到小堆中//并使用向下调整//这样每次来的比较大的数据就可以放到小堆中if (x > arr[0]) {arr[0] = x;AdjustDown(arr,k,0);}}//打印数据for (int i = 0; i < k;i++) {printf("%d ",arr[i]);}fclose(fout);}

四、完整代码

1.堆的代码

Heap.c

#include "Heap.h"//初始化堆
void InitHeap(Heap* hp) 
{assert(hp);hp->a = NULL;hp->capacity = 0;hp->size = 0;
}//销毁堆
void DestroyHeap(Heap* hp) 
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;	
}//交换两个数
void swap(HPDataType* s1,HPDataType* s2) 
{HPDataType tmp = *s1;*s1 = *s2;*s2 = tmp;
}
//向上调整
void AdjustUp(HPDataType * a,int child) 
{//先找到父结点的下标int parent = (child - 1) / 2;while (child > 0)	//child等于0时，说明已经调整ok了{if (a[child] > a[parent]){swap(&a[child], &a[parent]);//可能会向上调整多次child = parent;parent = (parent - 1) / 2;}else {break;}}
}//堆的插入
void PushHeap(Heap* hp, HPDataType x)
{assert(hp);//堆满判断if (hp->capacity == hp->size) {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;hp->size++;//堆的向上调整AdjustUp(hp->a,hp->size-1);
}//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{//先去找根结点的较大的孩子结点int child = 2 * parent + 1;//可能会向下调整多次while (child<size) {//这里使用假设法，先假设左孩子的值最大//如果不对就进行更新if ((child+1 < size)&&a[child] < a[child+1]) {child++;}//根结点与其孩子结点中的较大的一个进行交换if(a[child] > a[parent]) {swap(&a[child],&a[parent]);//更新下标parent = child;child = 2 * parent + 1;}else {break; //调完堆}}
}
//堆的删除
void PopHeap(Heap* hp)
{assert(hp);assert(hp->size>0);//头尾交换swap(&hp->a[0],&hp->a[hp->size-1]);hp->size--;//向下调整AdjustDown(hp->a,hp->size,0);
}//获取堆顶数据
HPDataType TopHeap(Heap* hp) 
{assert(hp);assert(hp->size>0);return hp->a[0];
}//获取堆的数据个数
int SizeHeap(Heap* hp)
{assert(hp);return hp->size;
}//堆的判空
bool EmptyHeap(Heap* hp) 
{assert(hp);return hp->size == 0;
}

Heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;	//指向动态数组int capacity;	//堆的容量int size;		//堆中数据个数
}Heap;//初始化堆
void InitHeap(Heap* hp);//销毁堆
void DestroyHeap(Heap* hp);//堆的插入
void PushHeap(Heap* hp, HPDataType x);//堆的删除
void PopHeap(Heap*hp);//获取堆顶数据
HPDataType TopHeap(Heap* hp);//获取堆的数据个数
int SizeHeap(Heap* hp);//堆的判空
bool EmptyHeap(Heap* hp);

test.c

#include "Heap.h"void Test1() 
{Heap hp;InitHeap(&hp);PushHeap(&hp,49);PushHeap(&hp,65);PushHeap(&hp,34);PushHeap(&hp,25);PushHeap(&hp,37);PushHeap(&hp,27);PushHeap(&hp,19);//删除65PopHeap(&hp);//printf("堆的个数：%d\n",SizeHeap(&hp));//while (!EmptyHeap(&hp)) //{//	printf("%d-", TopHeap(&hp));//	PopHeap(&hp);//}DestroyHeap(&hp);//27,19,34,65,49,25,37
}
int main() 
{Test1();return 0;
}

2. 堆排序的代码

//堆排序
void HeapSort(int* arr, int n) 
{int i = 0;//使用向下调整算法向上调整，把大的值调到上方。for (i = (n - 1 - 1) / 2; i >= 0;i--){//先找到数组最后端的父结点的下标//父结点的下标减一就是另一个//使用向下调整算法进行调整AdjustDown(arr,n,i);}//进行排序//因为是大堆，所以根结点的值是最值//把最值与堆的最后一个结点进行交换//再把交换后的根节点进行向下调整//然后堆的大小减一//注意end 是从n-1开始的(数组最后一个元素的下标)int end = n-1;while (end > 0) {//swap end = n-1 这表示下标swap(&arr[0],&arr[end]);//adjustdown 函数里面的end是元素的个数，所以不是先--end//所以AdjustDown(arr,end,0);end--;}
}