一：堆的概念及存储结构

简单点来说，堆就是完全二叉树，只不过这个完全二叉树有个特点：它的结点要么大于任意一个孩子结点，要么小于任意一个孩子结点。如果其结点大于任意一个孩子结点，就称其为大顶堆，反之如果其结点小于任意一个孩子结点，就称其为小顶堆。

于是对于大顶堆来说，其值最大的结点是根节点，对小顶堆来说，其值最小的结点也是根节点。这一点也是堆排序算法实现的核心，所以堆排序也叫做选择排序。

既然它是完全二叉树，所以适合用数组来存储

二：堆的实现（1）堆的结构体定义

堆是一个完全二叉树，所以使用一个数组来存储。存储时为了便于调整，依然使用动态增长的数组

（2）堆的初始化

使用堆的场景，或者是题目中一般是这样给出的：直接抛给你一个数组，这个数组对应了一个完全二叉树，初始化时就是要把这个数组进行复制，然后对这个二叉树进行调整，使其成为堆，再进行后续操作。

所以初始化参数里，要给出数组和元素个数

（3）堆的向下调整算法

堆的调整算法是堆的核心所在。上述数组中的完全二叉树还不是堆，这里用上图中的数组，以调整小顶堆为例，详细说明堆的调整过程

基本思路如图所示

调整代码如下

下面的这个动图所展示的就是调整过程：

上述代码中，有一个非常容易忽略的地方

补充：上面构建的是小顶堆，如果要构建大顶堆，代码只需稍微改动两个地方即可

（4）堆的构造

上面堆的向下调整算法要求左右子树必须是堆，但一般不会有这样的理想情况。那么为什么还要讲堆的向下调整算法呢？其实对于一个完全二叉树，从根节点角度看，确实满足不了情况。但是，去考察极限情况——一个结点就是一个完全二叉树，它也一定是一个堆，所以可以从最后一个非叶结点开始（也可以从最后一个结点开始，只不过，如果从最后一个结点开始效率不高），对每一个结点使用堆的向下调整，直到根节点，这样就能构造一个小顶堆了。如果一个完全二叉树有n个结点，那么它的最后一个非叶结点的编号为(n/2)-1。

如下

代码如下

（5）堆排序A：堆排序思想

从上面的叙述可以看出，堆建立后，对应数组是部分有序的，因为我们对堆元素大小的限制仅局限于父结点和孩子结点之间，对于左孩子和右孩子之间谁大谁小是不关心的。

那么堆排序从何而来呢？仔细观察，虽然不能保障堆是完全有序的，但是却能保证根结点是最大的（大顶堆）或最小的（小顶堆）。于是：我们可以每次选出一个根结点，将其划到有序序列里面，并对剩余结点进行调整，使剩余部分再次成为一个堆，然后对这个堆再进行上述操作，这也就是为什么堆排序属于选择排序的原因。

这里还有一个问题，当把根节点选出来后，剩余部分就没有根节点了，此时应该怎么做？是把它们再搞成一个完全二叉树，然后再进行建堆？仔细想想也不行，因为这样做时间复杂度就太高了，堆排序也就没有存在的意义了。

这里：选出根节点后，让根节点与此时无序序列中的最后一个结点（第一次选择的时候就和最后一个结点交换，第二次选择的时候和倒数第二个结点交换，以此类推）进行交换，此时根节点到达下方成为有序序列中的一员，新的结点到达根节点位置，由于这个结点到来，堆的结构被破坏，由于是根节点破坏了堆的结构，所以调用向下调整函数，只对根节点的位置进行调整，重新生成一个堆，然后重复上述操作。

以小顶堆为例，经过上述操作，每次根节点到达有序序列的前一个位置，于是整个数组成为了降序排列；以大顶堆为例，经过上述操作，整个数组就成为了升序排列。

于是就有：需要升序排序，就建立大顶堆，需要降序排序，就建立小顶堆。

B：堆排序演示

堆排序步骤：利用题目中给出的数字，建立完全二叉树，然后对这个完全二叉树进行建堆操作，接着根据题目要求，进行选择，调整，选择，调整······。

对本例的数组建立大顶堆，进行升序排序，过程如下

C：堆排序代码D：堆排序时间复杂度

堆排序时间复杂度为：O(nlgn)

推导过程如下：

（5）插入元素

还是以上述大顶堆为例，建好堆后，需要插入元素，此新元素插入到最后一个结点的下一个位置，由于这一个结点的到来，可能再次破坏了堆的结果，所以可以重新建立堆，但是仔细观察，其破坏的仅仅是一部分，如图

与向下调整算法相反，上图涉及的是向上调整算法，执行过程，代码与向下调整算法恰好相反

（6）删除元素

堆删除元素默认删除第一个，因为删除其它元素没有意义。删除时，将最后一个元素与第一个元素交换，然后对新的根进行向下调整即可

三：Top K问题

Top K问题：找出N个数当中最大的或者最小的前K个

解决方法1：排序

对于大多数人，想到的第一个方法自然就是排序。把这个N个数按一定顺序排序即可，然后找出取出前K个数。这种方法在N不太大的情况下是可以的，但是当N非常大的时，即便用最快的排序算法，最后花费的时间代价还是很高的，是一种不明智的解法。而且当N非常非常大时，内存中无法放下，就不能使用如堆排序这样的内部排序算法

解决方法2：；建堆

其实这也是堆这种结构真正的用途所在

假设用1万亿个数，需求是找出这一万亿个数中最大的前10个。，如果提示使用堆来解决，我们正常的反映就是建立大顶堆，每次取堆顶即可，但是这里会存在一个非常尴尬的情况：如果一万亿个数中前10个刚好就是最大的，那么这样的话堆排序就完全在做无用功了，虽然这种情况非常少见，但是它反映了这种建大顶堆的不可取之处。

相反，我们应该建立小顶堆，有K个数就建立K个数的小顶堆，比如这里前10个数建立小顶堆，然后从第11个数开始，只要比它堆顶的数大，就进入堆内，然后删除这个堆顶数据，然后调整，依次类推

如下：

在oj题中，这种求前K个的问题，频率还是挺高的

四：参考代码

Heap.h

#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <string.h>typedef int DataType;typedef struct Heap{	DataType* _arr;	int _length;	int _capacity;}Heap;void print(Heap* heap,int n);//打印void HeapInit(Heap* php, DataType* a, int n);//初始化void HeapDestroy(Heap* php);//销毁void AdjustDown(Heap* php, int n,int root);//向下调整：前提左右子树都是小堆void AdjustUp(Heap* php,int child);//向上调整，用于插入时void HeapCreat(Heap* php, int n);//建立堆void HeapPush(Heap* php, DataType x);//插入元素void HeapPop(Heap* php);//删除元素，删除头void HeapSort(Heap* php);//堆排序DataType HeapTop(Heap* php);

Heap.c

#pragma once#include "heap.h"void print(Heap* heap,int n){	assert(heap);	for (int i = 0; i <n; i++)	{		printf("%d ", heap->_arr[i]);	}	printf("\n");}void swap(DataType* p1, DataType *p2){	DataType temp = *p2;	*p2 = *p1;	*p1 = temp;	}void AdjustDown(Heap* php, int n, int root){	int parent = root;//待交换父节点	int child = parent * 2 + 1;//默认认为左孩子小	while (child<n)//一旦child>n，parent就到了最后一层，调整完成	{		if (child+1<n && php->_arr[child + 1] > php->_arr[child])			++child;//如果右孩子比较小，就让右孩子与父节点交换		if (php->_arr[child] > php->_arr[parent])//如果孩子小，孩子与父亲交换		{			swap(&php->_arr[child], &php->_arr[parent]);			parent = child;//交换完，同时向下移动，			child = child * 2 + 1;		}		else//如果不小于，就跳出，否则会一直陷入循环		{			break;		}	}}void AdjustUp(Heap* php, int child)//向上调整，用于插入{	int parent = (child - 1) / 2;//求出这个孩子的父亲	//while (parent>=0)//这样写是错误的，因为parent永远都不会小于0	while(child>0)//当child>0时，早该结束了	{		if (php->_arr[child] > php->_arr[parent])		{			swap(&php->_arr[child], &php->_arr[parent]);//调整大顶堆时，如果孩子大于父亲，就进行交换			child = parent;			parent = (child - 1) / 2;//与向下调整类似，只不过是向上跌打		}		else		{			break;		}	}}void HeapInit(Heap* php, DataType* a, int n){	assert(php);	php->_arr = (DataType*)malloc(sizeof(DataType)*n);	memcpy(php->_arr, a, sizeof(DataType)*n);	php->_length = n;	php->_capacity =php->_length= n;	//：从最后一个非叶结点开始，对每个结点进行向下调整}void HeapDestroy(Heap* php){	assert(php);	free(php->_arr);	php->_capacity = 0;}void HeapCreat(Heap* php, int n){	assert(php);	int i = 0;	for (i = n / 2 - 1; i >= 0; --i)//从最后一个非叶结点开始，对每个结点进行向下调整	{		AdjustDown(php, n, i);	}}void HeapSort(Heap* php){	assert(php);	for (int i = php->_capacity-1; i > 0; --i)//拿出最后一个结点放到根节点位置，然后再进行调整	{		swap(&php->_arr[0], &php->_arr[i]);		AdjustDown(php, i, 0);		print(php, php->_capacity);	}	}void HeapPush(Heap* php, DataType x)//插入元素时，只会影响一部分，所以仅对那一部分进行向上调整（）类似于并查集{	assert(php);	if (php->_length == php->_capacity)	{		php->_capacity *= 2;		DataType* temp = (DataType*)realloc(php->_arr,(sizeof(DataType))*(php->_capacity));		php->_arr = temp;	}	php->_arr[php->_length] = x;	php->_length++;	AdjustUp(php, php->_length-1);//调用向上调整算法	}void HeapPop(Heap* php){	assert(php);	assert(php->_length > 0);	php->_arr[0] = php->_arr[php->_length-1];	php->_length--;	AdjustDown(php, php->_length, 0);}

test.c

#pragma once#include "heap.h"void test(){	int a[] = { 27,15,19,18,28,34,65,49,25,37 };	Heap heap;	HeapInit(&heap, a, sizeof(a) / sizeof(DataType));	print(&heap, heap._capacity);//原始	HeapCreat(&heap, heap._capacity);//建大顶堆	print(&heap, heap._capacity);	//HeapSort(&heap);//排升序	HeapPush(&heap, 97);	//HeapPush(&heap, 63);	print(&heap, heap._length);	HeapPop(&heap);	print(&heap, heap._length);}int main(){	test();}