一、前言
前面我们学习了二叉树，知道了二叉树一般用链式存储，但是还有一种存储方式是顺序存储，而 普
通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用
顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
二、堆的概念及结构
n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。K(i) <= K(2i) 且 K(i) <= K(2i+1)称为小堆 或者 K(i) >= K(2i+1) 且 K(i) >= K(2i+1) 称为大堆。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
*堆中某个节点的值总是不大于或不小于其父节点的值。
* 堆总是一棵完全二叉树。
如下图
大根堆（大堆）
小根堆（小堆）
三、堆的实现
均以小堆为例
* 首先我们先来定义一个堆
typedef int HPDataType typedef struct Heap { HPDataType* a; //数组 int size; //元素个数 int capacity; //容量大小 }HP;
* 接着我们再来实现堆的各种接口函数
void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; } bool HeapEmpty(HP* php) { return php->size = 0; } void HeapDestory(HP* php); { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; } int HeapTop(HP* php) //取堆顶元素 { assert(php); assert(php->size > 0); return php->a[0]; } int HeapSize(HP* php) //堆的大小 { assert(php); return php->size; }
* 接下来我们就来实现堆的插入数据和删除数据的函数
1、堆的插入：先插入一个数到数组的尾上，再进行向上调整算法，直到满足堆。
向上调整算法：
void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; } void AdjustUp(HPDatatype* a, int child) { int parent = (child - 1) / 2; while(child > 0) { if(a[child] < a[parent]) { swap(&a[child], &a[parent]); } else { break; } child = parent; parent = (child - 1) / 2; } }
插入函数
void HeapPush(HP* php, HPDatatype x) { assert(php); if(php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if(tmp == NULL) { printf("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size - 1); }
2、堆的删除：删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
向下调整算法：
void AdjustDown(HeapDatatype* a, int size, int parent) { int child = parent * 2 + 1; //默认左孩子最小 while(child < size) { if(a[child] > a[child + 1] && child + 1 < size) { child++; } if(a[parent] > a[child]) { swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } }
删除函数
void HeapPop(HP* php) /*删除堆顶的数据，将第一个和最后一个交换， 删除最后一个利用向下调整算法将其重新调整为堆*/ { assert(php); assert(php->size > 0); swap(&php->a[0], &php->a[php->size-1]); php->size--; AdjustDown(php->a, php->size, 0); }
四、堆的应用
1、TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决。
基本思路如下：
* 用数据集合中前K个元素来建堆 ：前k个最大的元素，则建小堆 ，前k个最小的元素，则建大堆。
* 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。
* 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(int* a, int n, int k) { //1、建堆——用a中前k个元素建堆 int* kMinHeap = (int*)malloc(sizeof(int) * k); assert(kMinHeap); for(int i = 0; i < k; i++) { kMinHeap[i] = a[i]; } for(int i = (k-1-1) / 2; i>=0; i--) { AdjustDown(kMinHeap, k, i); } //2、将剩余n-k个元素依次与堆顶元素比较并交换 for(int j = k; j < n; j++) { if(kMinHeap[0] < a[j]) { kMinHeap[0] = a[j]; AdjustDown(kMinHeap, k, 0); } } for (int i = 0; i < k; i++) { printf("%d ", kMinHeap[i]); } }
2、堆还有一个应用就是应用在堆排序中，堆排序即利用堆的思想来进行排序。这里我们不做讲解，而会在排序中专门讲解。
