【二叉树的顺序结构：堆 && 堆排序 && TopK]

努力提升自己，永远比仰望别人更有意义

---

目录

 

1 二叉树的顺序结构

2 堆的概念及结构

3 堆的实现

3.1 堆向下调整算法

 3.2 堆向上调整算法

 3.3堆的插入

 3.4 堆的删除

3.5 堆的代码实现

4 堆的应用

4.1 堆排序

4.2 TOP-K问题

总结：

---

1 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

---

2 堆的概念及结构

如果有一个关键码的集合 K = { k0 ，k1 ，k2 ，k3 … ，} ，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <=K2i+1 且 Ki<=K2i+2 ( i = 0 ， 1 ， 2… )，则称为小堆 (反之则大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树

---

3 堆的实现

3.1 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提： 左右子树必须是一个堆，才能调整。

int array [] = { 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 };

 具体代码：

void AdjustDown(int* a, int parent, int sz)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz && a[child + 1] > a[child])//建立小堆 a[child + 1] < a[child]
			child++;
 
		if (a[child] > a[parent])//建立小堆 <
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
 
}

这里建立的是大堆，建立小堆代码中我给了注释.

 3.2 堆向上调整算法

堆的向上调整算法往往与push相搭配，push完一个数据就将该数据向上调整，这样就能够保证堆的结构不会被破坏。

具体图例：

代码实现：

void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了
	{
		if (a[child] > a[parent])//建小堆 <
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

 我们不难发现一个数据向上调整或者向下调整的时间复杂度都为logN.

 3.3堆的插入

具体图例：

 代码实现：

void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->sz)
	{
		int newcapacity = php->a == NULL ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	php->a[php->sz] = x;
	php->sz++;
	//向上调整算法，保证建立的是堆（这里以建小堆为例）
	AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标
}

 3.4 堆的删除

假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。

代码实现：

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);
	//假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，
	//否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。
 
	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	AdjustDown(php->a, 0, php->sz);
}

3.5 堆的代码实现

#include
#include
#include
#include
 
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* a;
	int sz;
	int capacity;
}Heap;
 
void HeapInit(Heap* php);
void HeapPush(Heap* php, HeapDataType x);
void HeapPop(Heap* php);
HeapDataType HeapTop(Heap* php);
int HeapSize(Heap* php);
bool HeapEmpty(Heap* php);
void HeapDestroy(Heap* php);
void HeapPrint(Heap* php);
void AdjustDown(int* a, int parent, int sz);
void AdjustUp(int* a, int child);
void Swap(HeapDataType* p1, HeapDataType* p2);
 
void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->sz = 0;
}
 
 
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
 
void AdjustUp(int* a, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)//用parent>=0也行，只是这样的话就不是正常结束的了
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
 
 
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->sz)
	{
		int newcapacity = php->a == NULL ? 4 : php->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	php->a[php->sz] = x;
	php->sz++;
	//向上调整算法，保证建立的是堆（这里以建小堆为例）
	AdjustUp(php->a, php->sz - 1);//第二个参数传的是push这个数据的下标
}
 
 
void AdjustDown(int* a, int parent, int sz)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz && a[child + 1] > a[child])
			child++;
 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
 
}
 
 
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);
	//假设建小堆，要pop掉最小的一个数值（堆顶），要让下面的结构继续保持小堆结构就不能只将数据向前挪动一位，
	//否则堆的结构将会被破坏。正确做法是将堆顶的数据与最后一个数据交换，然后重新向下建堆，再pop掉堆尾数据。
 
	Swap(&php->a[0], &php->a[php->sz - 1]);
	php->sz--;
	AdjustDown(php->a, 0, php->sz);
}
 
 
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->sz > 0);
 
	return php->a[0];
	
}
 
 
int HeapSize(Heap* php)
{
	assert(php);
	return php->sz;
}
 
 
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->sz == 0;
}
 
 
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->capacity = php->sz = 0;
}
 
 
void HeapPrint(Heap* php)
{
	assert(php);
	for (int i = 0; i < php->sz; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

---

4 堆的应用

4.1 堆排序

在这里我们思考一个问题：排序是向上建堆还是向下建堆？

口说无凭，这里我们可以通过准确的计算来算出他们各自的时间复杂度：

1 向上建堆：

这里我们都以满二叉树为例，时间复杂度算的只是一个大概值所以可以用满二叉树来代替完全二叉树。（假设数的高度为h)

第一层有2^0个结点，要向上调整0次；

第二层有2^1个结点，要向上调整1次；

第三层有2^2个结点，要向上调整2次；

…………………………

第h-1层有2^(h-2)个结点，要向上调整(h-2)次；

第h层有2^(h-1)个结点，要向上调整(h-1)次；

所以可得：

T(h)=2^1*1+2^2*2+……2^(h-2)*(h-2)+2^(h-1)*(h-1)

利用错位相减法很容易算出：

T(h)=2^h*(h-2)+2;

由于h=logN(大概值就行，不用太精确）

所以求得向上建堆的时间复杂度大概在：

T(N)=N*logN  这个数量级。

2 向下建堆：

这个计算我在讲堆排序的时候计算过，大家可以跳转到堆排那里：

八大排序之插入和选择排序

通过计算我们可以知道向下建堆的时间复杂度大概在：

T(N)=N  这个数量级。

所以我们选用向下建堆。

那么第二个问题来了：排升序是建大堆还是建小堆？

如果建小堆，最小数已经被选出来了，但是不能够pop掉最小数，否则堆结构将被破环，那么又要重新建堆，这样就没有了效率，所以我们要建大堆，将堆顶元素与最后一个元素交换再--数据个数，然后向下调整。

具体代码：

void HeapSort(HeapDataType* a, int sz)
{
	//从最后一个结点的父亲开始建堆
	for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, i, sz);
	}
 
	for (int i = sz-1; i>0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, 0, --sz);
	}
}

4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。

对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前 K 个元素来建堆 ：

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素 ：

将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。

具体代码：

    //建立一个k个数的小堆，依次遍历数组，比堆顶元素大就替换，然后向下调整,最后堆中数据就是topk
	//时间复杂度为：N+N*logk  空间复杂度为O(k)
	int topk[5] = {0};
	int i;
	for (i = 0; i < 5; i++)
	{
		topk[i] = array[i];
	}
	//建小堆
	for (i = (5 - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk, i, 5);
	}
	//遍历替换
	for (i=5; i < sz; i++)
	{
		if (array[i] > topk[0])
		{
			topk[0] = array[i];
			AdjustDown(topk, 0, 5);
		}
	}
 
	for (i = 0; i < 5; i++)
		printf("%d ", topk[i]);
	//这种方法占据内存较小，比较优秀

---

总结：

文章中我们介绍了堆这种二叉树顺序结构，实现了堆并且将堆的两大比较重要的应用（堆排序和TopK问题）介绍了，这里面比较重要的就是向上/向下调整算法。后面链式二叉树以及相关OJ我们将放在下一篇文章来讲解，大佬们，我们下期再见！