堆(建堆算法，堆排序)

目录

一.什么是堆？

1.堆 

2.堆的储存 

二.堆结构的创建

1.头文件的声明：

2.向上调整

3.向下调整 

4.源码： 

三.建堆算法

1.向上建堆法

2.向下建堆法

四.堆排序

五.在文件中Top出最小的K个数

---

一.什么是堆？

1.堆 

        堆就是完全二叉树，而且是一种特殊的完全二叉树，它需要满足每一个父节点都大于子节点，称为大堆，或每一个父节点都小于子节点，称为小堆。而对兄弟节点之间的大小关系并没有要求(为此它并不是有序的)。如下：

2.堆的储存 

         对于完全二叉树有一个更好的储存方法，就是用顺序表来储存，相比链式储存使用顺序表储存的一个很大的好处在于知道一个结点可以很容易的算出它父结点和子结点的下标，还有可以随机访问。

父子结点下标计算公式 ：

        左子结点下标 = 父结点下标*2+1

        右子结点下标 = 父结点下标*2+2

        父结点下标 = (子结点下标-1) / 2 

二.堆结构的创建

1.头文件的声明：

Heap.h

#pragma
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define HpDataType int
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size;int cap;
}Heap;
void HeapInit(Heap* php);//堆的初始化
void HeapDestory(Heap* hp);//堆的销毁
void HeapPush(Heap* hp, HPDataType x);//堆的插入
void HeapPop(Heap* hp);//堆的删除
HPDataType HeapTop(Heap* hp);//取堆顶的数据
int HeapSize(Heap* hp);//堆的数据个数
int HeapEmpty(Heap* hp);//堆的判空void AdjustUP(HpDataType* arr, int child);//向上调整
void AdjustDOWN(HpDataType* arr, int size, int parent);//向下调整
void Swap(HpDataType* a, HpDataType* b);//元素的交换

        其中堆的初始化，堆的销毁，堆的数据个数，堆的判空，和取堆顶数据和顺序表的操作是一样的这里重点来学一下堆的插入，堆的删除。

2.向上调整

        插入元素呢直接往数组最后插入就可以，但是插入后就不一定是堆结构的，所以需要调整。例如一个大堆：

向大堆中插入53

调整后：

代码示例：

void AdjustUP(HpDataType* arr,int child)
{int parent = (child - 1) / 2;//计算父节点下标while (child>0)//注意这里不能是parent>0{if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);//封装一个函数进行交换child = parent;//更新子节点parent = (child - 1) / 2;//更新父节点}elsebreak;}
}

★如果是小堆只需要把if条件的大于号改为小于号

3.向下调整 

        要注意删除元素我们删除的不是尾元素，这样毫无意义，我们删除的是下标为0位置的元素，它是整个堆中最小或最大的元素。怎么删除呢？直接将它删除然后后面的元素在覆盖上吗？这样做的话，它就不是堆了，而且元素之间关系将会全部混乱，就需要从0开始创建堆，效率非常低，我们可以把首元素与尾元素互换然后删除尾元素，虽然这个操作过后它也可能就不是堆了，不过我们可以将首元素向下调整，让它成为堆。比刚才的方案效率要高得多。

比如我们删除大堆中的一个元素

调整过程：

调整后的结果：

代码示例：

void AdjustDOWN(HpDataType* arr, int size, int parent)
{int child = parent * 2 + 1;while (child < size){if ((child+1)<size&&arr[child] < arr[child + 1])child++;if (arr[child] > arr[parent]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}

★如果是小堆只需要把if条件里兄弟节点的大小关系和父子节点的大小关系改变一下就行

4.源码： 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapInit(Heap* ps)//初始化
{assert(ps);ps->arr = NULL;ps->cap = ps->size = 0;
}
void HeapDestory(Heap* hp)//销毁堆
{assert(hp);free(hp->arr);hp->cap = hp->size = 0;
}
void Swap(HpDataType* a, HpDataType* b)//交换元素
{HpDataType c = *a;*a = *b;*b = c;
}
void AdjustUP(HpDataType* arr,int child)//向下调整
{int parent = (child - 1) / 2;while (child>0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}
void AdjustDOWN(HpDataType* arr, int size, int parent)//向上调整
{int child = parent * 2 + 1;while (child < size){if (arr[child] > arr[child + 1])child++;if ((child+1)<size&&arr[child] < arr[parent]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}elsebreak;}
}
void HeapPush(Heap* ps, HPDataType x)//插入元素
{assert(ps);if (ps->size == ps->cap){int pnc = ps->cap == 0 ? 4 : 2 * ps->cap;HpDataType* pnew = realloc(ps->arr, sizeof(HPDataType)*pnc);assert(pnew);ps->arr = pnew;ps->cap = pnc;}ps->arr[ps->size] = x;ps->size++;AdjustUP(ps->arr, ps->size - 1);
}
void HeapPop(Heap* hp)//删除元素
{assert(hp);assert(hp->size);if (hp->size == 1){hp->size--;return;}Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));hp->size--;AdjustDOWN(hp->arr, hp->size, 0);
}
HPDataType HeapTop(Heap* hp)//取堆顶元素
{assert(hp);assert(hp->size);return hp->arr[0];
}
int HeapSize(Heap* hp)//计算堆元素个数
{assert(hp);return hp->size;
}
int HeapEmpty(Heap* hp)//判断堆是否为空
{assert(hp);return hp->size == 0;
}

三.建堆算法

        在学习建堆算法的时候我们以对数组建堆为例，就是把数组的数据之间的关系做成一个堆结构，一般有两种方法，向上调整建堆和向下调整建堆，具体怎么做我们来看下面。

1.向上建堆法

        向上建堆法也就是通过向上调整建堆，我们拿到一个数组后可以把数组的首元素当做堆，第二个元素当做把新的元素插入堆，然后通过向上调整构成新的堆，以此类推下去把数组遍历完后一个堆就建成了。时间复杂度为O(N*logN)

代码示例：

#include<stdio.h>
#include"Heap.h"
int main()
{int arr[] = { 1,9,3,7,6,4,2,10,8,5 };int size = sizeof(arr) / sizeof(int);for (int i = 0; i < size; i++)AdjustUP(arr, i);//该函数在上文已给出，这里不再展示printf("建大堆后：\n");for (int i = 0; i < size; i++)printf("%d ", arr[i]);return 0;
}

 不过该方法相比向下调整建堆效率比较低，我们来看向下调整建堆法。

2.向下建堆法

        向下建堆法也就是通过向下调整建堆，要注意并不是从首元素开始调整，因为刚开始它并不满足左右子树都是堆结构，所以不能直接从第一个元素开始向下调整。既然要满足左右子树都是堆那么我们可以考虑从最后一个元素开始调整，不过最后一层下面已经没有元素了，它已经是堆，并不用调整，那么我们从倒数第二层开始调整，所以我们先来计算一下倒数第二层最后一个父节点的下标：

                (size-1-1)/2

        第一个size-1得到二叉树的最后一个元素的下标，再减一除以二得到它的父节点的下标。

代码示例：

#include<stdio.h>
#include"Heap.h"
int main()
{int arr[] = { 1,9,3,7,6,4,2,10,8,5 };int size = sizeof(arr) / sizeof(int);for (int i = (size - 1 - 1) / 2; i >= 0; i--)AdjustDOWN(arr, size,i);//该函数在上文已给出，这里不再展示printf("建大堆后：\n");for (int i = 0; i < size; i++)printf("%d ", arr[i]);return 0;
}

它的时间复杂度为O(N)证明如下： 

其中Sn为总的调整次数. 

四.堆排序

        给一个数组建堆后利用堆的性质给数组排序，使其效率更高，这就是一个堆排序。比如现在要对一个数组进行堆排序，第一个问题就是建大堆还是小堆，怎么利用堆来给数组排序。

        要进行升序就需要建大堆，如果建的是小堆，那么堆顶也就是首元素就是最小的元素，并不需要动，那么来处理第二个元素就注意到它并不一定是第二小的元素，只能从第二个元素开始重新建一个小堆，那么每排一个元素都需要重新建一个小堆效率就会变得很低。

        升序建大堆的话，第一个元素就是最大的元素，我们可以让它与最后一个元素互换，然后把堆的元素个数减一(就是把最后一个元素当做是堆外)，最后把堆顶元素向下调整，反复操作直到堆的元素个数变为了零。这样一个数组就按升序排好了。

        降序需要建小堆，原理和排升序相同这里就不在赘述。

代码示例：

#include<stdio.h>
#include"Heap.h"
int main()
{int arr[] = { 1,9,3,7,6,4,2,10,8,5 };int size = sizeof(arr) / sizeof(int);for (int i = (size - 1 - 1) / 2; i >= 0; i--)AdjustDOWN(arr, size,i);printf("建大堆后：\n");for (int i = 0; i < size; i++)printf("%d ", arr[i]);while (size){Swap(&arr[0], &arr[size - 1]);//交换元素size--;AdjustDOWN(arr, size, 0);}printf("\n排序后；\n");for (int i = 0; i < sizeof(arr) / sizeof(int); i++)printf("%d ", arr[i]);return 0;
}

五.在文件中Top出最小的K个数

        用堆结构的一个好处就在于，不需要排序就能高效的找出最小的前n个元素或最大的前n个元素，现在我们来利用堆来尝试找出文件中最小的K个数，一个比较低效的一个方法就是把文件中涉及到的所以数据都取出来然后把它建成一个小堆，然后Pop出前k次，得到最小的k个数。但是如果这个数据非常的大呢，比如有上亿个数据，那么就会消耗很大的内存空间。

        有一个很优的方法就是只取出文件的前K个数建成一个大堆，也就是说这个堆只用储K个元素，那么堆顶就是这个堆的最大元素，然后继续遍历文件每遍历一个元素都与堆顶元素作比较，如果比堆顶元素小就更新一下堆顶元素(把小的那个变成堆顶元素)，然后进行向下调整，直到遍历完整个文件，那么此时堆中的元素就是文件中最小的K个元素。此方法在时间复杂度上与上一方法差不多，但它大大的节省了空间。

代码示例：

#include<stdio.h>
#include"Heap.h"
void CreateNDate()
{//造数据，写入文件中int n = 10000;srand((unsigned int)time(NULL));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() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void PrintTopK(int k)
{int* arr = (int*)malloc(sizeof(int) * k);assert(arr);FILE* fop = fopen("data.txt", "r");if (!fop){perror("fopen error");return;}for (int i = 0; i < k; i++)//先取出k个建大堆fscanf(fop, "%d", &arr[i]);for (int i = (k - 1 - 1) / 2; i >= 0; i--)AdjustDOWN(arr, k, i);int x = 0;while (fscanf(fop, "%d", &x) != EOF){if (arr[0] > x){arr[0] = x;AdjustDOWN(arr, k, 0);}}for (int i = 0; i < k; i++)//输出堆中元素printf("%d ", arr[i]);
}
int main()
{CreateNDate();int k = 0;scanf("%d", &k);PrintTopK(k);return 0;
}