概念

堆是二叉树顺序存储的主要表现形式
其中任意一节点的值都>=或<=其孩子节点的值，称之为最大/小堆。
注： 堆一定是完全二叉树

堆的实现

1、向上调整

给一个堆中插入一个数据，如下图：

此处可采用向上调整，过程如下：




代码实现：

void AdjustUp(HPDataType* a, int child){assert(a);//小堆while (child > 0){int parent = (child - 1) / 2;if (a[child] < a[parent])//关键{Swap(&a[child], &a[parent]);child = parent;}elsebreak;}}

2、向下调整

目的也是调整为堆，但要求左右子树都是堆





代码实现：

void AdjustDown(HPDataType* a, int parent, int size){assert(a);int child = 2 * parent + 1;while (child < size){//选小的为孩子//child + 1 < size：防止越界if (a[child + 1] < a[child] && child + 1 < size);child++;if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}elsebreak;}}

堆的创建

根据堆的性质，堆的创建可利用上述的向上调整和向下调整来建堆。

1、向上调整建堆

向上调整的函数声明：void AdjustUp(HPDataType* a, int child);
一下列数组为例： int a[] = { 27,15,19,18,28,34,65,49,25,37};

以调大堆为例，调堆过程如下：

代码实现如下：

for (int i = 1; i < sz; i++){AdjustUp(a, i);}

如果child从a[sz]开始向上调整，对于调整过的部分不会有多次检查调整。

时间复杂度：O（N*log N）

2、向下调整建堆

向下调整的函数声明：void AdjustDown(HPDataType* a, int parent, int size);
同样的数组为例： int a[] = { 27,15,19,18,28,34,65,49,25,37};
以调大堆为例，向下调堆过程如下：

代码实现如下：

for (int i = (sz - 1 - 1) / 2; i >= 0; i--){//向下调整的前提是子树都是堆，//从倒数第一个非叶节点开始调//左右子树都可以调为堆AdjustDown(a, i, sz);}

时间复杂度：O（N）

堆的代码实现

typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;

堆的构建

void HeapInit(HP* p){assert(p);p->a = NULL;p->size = p->capacity = 0;}

堆的销毁

void HeapDestroy(HP* p){assert(p);free(p->a);p->size = p->capacity = 0;}

堆的插入

void HeapPush(HP* p, HPDataType d){assert(p);//插入数据与最后一个节点if (p->size == p->capacity){//没空间了int newcapacity = p->size == 0 ? 4 : 2 * p->capacity;HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * newcapacity);if (!tmp){perror("HeapPush realloc");exit(-1);}p->a = tmp;p->capacity = newcapacity;}p->a[p->size++] = d;//调整AdjustUp(p->a, p->size - 1);}

堆的删除

一般删除堆顶数据，删其他的没啥意义。
删除方式：将最后一个叶节点和堆的根节点互换，size–后，根节点的左右子树为堆，再向下调整。

void HeapPop(HP* p){assert(p);assert(p->size > 0);//交换//HPDataType tmp = p->a[0];//p->a[0] = p->a[0];//p->a[p->size - 1] = tmp;Swap(&p->a[0], &p->a[p->size - 1]);p->size--;AdjustDown(p->a, 0, p->size);}

取堆顶的数据

HPDataType HeapTop(HP* p){assert(p);assert(p->size > 0);return p->a[0];}

堆的数据个数

int HeapSize(HP* p){return p->size;}

堆的判空

bool HeapEmpty(HP* p){assert(p);return p->size == 0;}

TopK问题（找最大的前K个）

1、排序 O（N*log N)

利用上述的建堆方式，将堆顶数据pop——调整——pop，最后得到有序的数组。
注：排升序，建大堆，大的数据pop后排在后面；反之，排降序，建小堆。

2、建立N个数的大堆，Top/Pop K 次 ，O（N+log N*K）

3、假设N很大，如N=100亿，K=100.

解决方案：
1、前k给数建立小堆
2、剩下N-K个数和堆顶比较，调整，最后堆中数据是前K个最大值。

好看字体下载