【数据结构】堆的实现，堆排序以及TOP-K问题

太过爱你忘了你带给我的痛 2023-10-14 19:18 121阅读 0赞

## ![7f12384a48d04dba8660177353fcc859.gif][] ##

**目录**

1.堆的概念及结构

2.堆的实现

2.1初始化堆

2.2销毁堆

2.3取堆顶元素

2.4返回堆的大小

2.5判断是否为空

2.6打印堆

2.7插入元素

2.8堆的向上调整

2.9弹出元素

2.10堆的向下调整

3. 建堆时间复杂度

4. 堆的应用

4.1 堆排序

4.2 TOP-K问题

--------------------

## 1.堆的概念及结构 ##

堆是一种数据结构，它是由一组元素组成的，并按照一定的规则进行排序和访问。堆可以看作是一个完全二叉树，其中**每个节点的值都大于或等于其子节点（对于最大堆）**或**小于或等于其子节点（对于最小堆）**。堆通常用来解决具有优先级的问题，例如找到最大或最小的元素。

![e2422773c60d463389abe9b0c48a9219.png][]

堆的性质：

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

![60da87b8a42f4851b1da1acab57fe631.png][]

## 2.堆的实现 ##

这里写的是小根堆，大根堆可以在小根堆的基础上稍作修改。下面是堆要实现的一些接口函数：

//初始化堆
    void HeapInit(HP* php);
    //销毁堆
    void HeapDestory(HP* php);
    //插入元素
    void HeapPush(HP* php, HPDataType x);
    //堆向上调整算法
    void AdjustUp(HP* php, int x);
    //弹出堆顶元素
    void HeapPop(HP* php);
    //堆向下调整算法
    void AdjustDwon(HPDataType* a, int size, int x);
    //取堆顶元素
    HPDataType HeapTop(HP* php);
    //返回堆的大小
    int HeapSize(HP* php);
    //判断是否为空
    bool HeapEmpty(HP* php);
    //打印堆
    void HeapPrint(HP* php);

堆的定义：

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

对于一些简单的接口函数，我们就不详细介绍了，在堆中，我们主要要学习的是向上调整算法和向下调整算法。这两个函数分别在插入元素和弹出元素的时候会调用。

### 2.1初始化堆 ###

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

### 2.2销毁堆 ###

void HeapDestory(HP* php)
    {
    	assert(php);
    	free(php->a);
    	php->a = NULL;
    	php->size = php->capacity = 0;
    }

### 2.3取堆顶元素 ###

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

### 2.4返回堆的大小 ###

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

### 2.5判断是否为空 ###

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

### 2.6打印堆 ###

void HeapPrint(HP* php)
    {
    	assert(php);
    	for (int i = 0; i < php->size; i++)
    	{
    		printf("%d ", php->a[i]);
    	}
    	printf("\n");
    }

### 2.7插入元素 ###

向堆中插入一个元素，我们可以将这个元素插入到堆的尾部，因为堆的实际存储结构是一个数组，我们可以将元素放到数组末尾，但如果仅仅是插入到数组末尾的话，会将堆的结构给破环，我们还需要调用一个向上调整的函数，来调整各个节点间的大小关系。

**在插入之前，需要判断堆的容量是否足够，如果堆的容量已满，需要扩容**，这里每次扩容实在原来的基础上扩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\n");
    			exit(-1);
    		}
    		php->a = tmp;
    		php->capacity = newCapacity;
    	}
    
    	php->a[php->size] = x;
    	AdjustUp(php->a, php->size);//向上调整
    	php->size++;
    }

### 2.8堆的向上调整 ###

在上面插入元素的过程中，我们已经使用了堆的向上调整算法，下面，我们来看看怎么实现这个向上调整算法吧：

![b86af2d1bf7e4264a3ce5589017c5c89.png][]

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

图示过程：

![43750a006b294b5b8e7dbee21562abe2.png][]

void AdjustUp(HPDataType* a, int x)
    {
    	int child = x;
    	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;
    	}
    }

代码分析：

1.  初始化变量child为节点x，parent为其父节点的索引，也即 (child - 1) / 2。
2.  进入一个循环，该循环会一直执行直到节点x上浮到合适的位置或者到达堆顶。
3.  在循环中，判断节点x的值是否小于其父节点的值，若成立则交换两者的值。
4.  若节点x的值不小于父节点的值，则跳出循环，因为此时堆的性质已满足。
5.  更新child和parent的值，将child更新为parent，parent更新为其父节点的索引，也即 (child - 1) / 2。
6.  重复步骤3-5，直到节点x的值大于或等于其父节点的值，或者到达堆顶。

### 2.9弹出元素 ###

弹出元素就是将堆顶的元素给删除，但我们不能直接进行删除，这样会将堆的结构给破坏，正确的方法是先将堆顶的元素和最后的元素进行交换，这样保证的首元素的左子树和右子树依然是堆的形态，然后将size自减，最后调用一个堆的向下调整函数。

![b2108763806f45a4a649878a2d86d1b4.png][]

void HeapPop(HP* php)
    {
    	assert(php);
    	Swap(&php->a[0], &php->a[php->size-1]);
    	php->size--;
    	AdjustDwon(php->a, php->size, 0);
    }

### 2.10堆的向下调整 ###

堆的向下调整：每次将父节点和左右孩子的较小值进行交换（小根堆），不断地更新父节点的孩子节点的值。

![d523beb6d95b4acea59b1a88aa58eaa1.png][]

void AdjustDwon(HPDataType* a, int size, int x)
    {
    	int parent = x;
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
    		if (child + 1 < size && a[child + 1] < a[child])
    		{
    			child++;
    		}
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    		}
    		else
    		{
    			break;
    		}
    		parent = child;
    		child = parent * 2 + 1;
    	}
    }

1.  初始化变量parent为节点x，child为其左子节点的索引，也即 parent \* 2 + 1。
2.  进入一个循环，该循环会一直执行直到节点x下沉到合适的位置或者没有子节点。
3.  在循环中，首先判断节点x是否有右子节点，并且右子节点的值小于左子节点的值，如果成立则将child更新为右子节点的索引。
4.  接着判断节点x的值是否大于其子节点的值，若成立则交换两者的值。
5.  若节点x的值不大于子节点的值，则跳出循环，因为此时堆的性质已满足。
6.  更新parent和child的值，将parent更新为child，child更新为parent的左子节点的索引，也即 parent \* 2 + 1。
7.  重复步骤3-6，直到节点x的值小于或等于其子节点的值，或者没有子节点。

## 3. 建堆时间复杂度 ##

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

**向下调整：**

![9657c1f359d9438e9b36bf31c09a76bd.png][]

因此：向下调整建堆的时间复杂度为O(N)。

**向上调整：**

![257afd6adaa749eaa415b5e7b19321f5.png][]

因此：向上调整建堆的时间复杂度为N\*logN;

## 4. 堆的应用 ##

### 4.1 堆排序 ###

利用堆排序数组并打印出来：

void testHeapSort()
    {
    	HP hp;
    	HeapInit(&hp);
    
    	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
    	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    	{
    		HeapPush(&hp, a[i]);
    	}
    	while (!HeapEmpty(&hp))
    	{
    		printf("%d ", HeapTop(&hp));
    		HeapPop(&hp);
    	}
    	//释放内存
    	HeapDestory(&hp);
    }
    int main()
    {
    	testHeapSort();
    	return 0;
    }

输出结果：

![30167d20cc704bedabf079fe8d8bfc8a.png][]

但是，使用这种方法是不是有点复杂了呢？我们要进行堆排序，还得先写一个堆的数据结构，当然并不是这样的，我们可以将代码进行修改，在原数组上进行建堆：

思路：

对于在原数组上进行建堆，我们可以使用两种方式：

第一种是向上建堆，向上建堆的时间复杂度是 O(N\*logN)，我们不推荐使用这种方法。

第二种是向下建堆，它的时间复杂度是O(N），它的效率比向上建堆要高。我们推荐使用向下建堆。

还有一个比较让人难以理解的一点是：**如果要进行升序，我们要建大堆，如果要进行降序，我们要建小堆。**

![69b4caca92db4246b31deb14251c4a3c.png][]

void swap(int* x, int* y)
    {
    	int tmp = *x;
    	*x = *y;
    	*y = tmp;
    }
    void HeapSort(int* a, int n)
    {
    	//从倒数第一个非叶子节点开始调
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDwon(a, n, i);//向下调整建堆
    	}
    	int end = n - 1;
    	while (end > 0)
    	{
    		swap(&a[0], &a[end]);
    		AdjustDwon(a, end, 0);//向下调整[0,end]的元素
    		--end;
    	}
    }
    int main()
    {
    	int a[] = { 1,4,7,5,10,2,8,9,3,6 };
    	int n = sizeof(a) / sizeof(a[0]);
    	HeapSort(a,n);//堆排序
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	return 0;
    }

### 4.2 TOP-K问题 ###

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

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

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

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

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

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

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

> 实际应用：在10000000个随机数中找出前十个最大的数字

void AdjustDwon(int* a, int size, int x)
    {
    	int parent = x;
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
    		if (child + 1 < size && a[child + 1] < a[child])
    		{
    			child++;
    		}
    		if (a[child] < a[parent])
    		{
    			int tmp = a[child];
    			a[child] = a[parent];
    			a[parent] = tmp;
    		}
    		else
    		{
    			break;
    		}
    		parent = child;
    		child = parent * 2 + 1;
    	}
    }
    
    void PrintTopK(int* a, int n, int k)
    {
    	int* KMaxHeap = (int*)malloc(sizeof(int) * k);
    	assert(KMaxHeap);
    	for (int i = 0; i < k; i++)
    	{
    		KMaxHeap[i] = a[i];
    	}
    	//建小根堆
    	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    	{
    		AdjustDwon(KMaxHeap, k, i);
    	}
    	//依次比较a数组中剩余的元素
    	for (int i = k; i < n; i++)
    	{
    		if (a[i] > KMaxHeap[0])
    		{
    			KMaxHeap[0] = a[i];
    		}
    		AdjustDwon(KMaxHeap, k, 0);
    	}
    	//打印
    	for (int i = 0; i < k; i++)
    	{
    		printf("%d ", KMaxHeap[i]);
    	}
    }
    void testTopK()
    {
    	srand(time(0));
    	int n = 10000000;
    	int* a = (int*)malloc(sizeof(int) * n);
    	for (int i = 0; i < n; i++)
    	{
    		a[i] = rand() % n;//a[i]的范围[1,n]
    	}
    	//手动设定10个最大的数
    	a[2] = n + 3;
    	a[122] = n + 5;
    	a[1233] = n + 1;
    	a[12333] = n + 2;
    	a[1322] = n + 8;
    	a[2312] = n + 6;
    	a[54612] = n + 7;
    	a[546612] = n + 9;
    	a[5612] = n + 10;
    	a[46612] = n + 4;
    	PrintTopK(a, n, 10);
    }
    int main()
    {
    	testTopK();
    	return 0;
    }

![28dc5ae4251c43c79a5ff8746096a8c5.gif][]

[7f12384a48d04dba8660177353fcc859.gif]: https://img-blog.csdnimg.cn/7f12384a48d04dba8660177353fcc859.gif
[e2422773c60d463389abe9b0c48a9219.png]: https://img-blog.csdnimg.cn/e2422773c60d463389abe9b0c48a9219.png
[60da87b8a42f4851b1da1acab57fe631.png]: https://img-blog.csdnimg.cn/60da87b8a42f4851b1da1acab57fe631.png
[b86af2d1bf7e4264a3ce5589017c5c89.png]: https://img-blog.csdnimg.cn/b86af2d1bf7e4264a3ce5589017c5c89.png
[43750a006b294b5b8e7dbee21562abe2.png]: https://img-blog.csdnimg.cn/43750a006b294b5b8e7dbee21562abe2.png
[b2108763806f45a4a649878a2d86d1b4.png]: https://img-blog.csdnimg.cn/b2108763806f45a4a649878a2d86d1b4.png
[d523beb6d95b4acea59b1a88aa58eaa1.png]: https://img-blog.csdnimg.cn/d523beb6d95b4acea59b1a88aa58eaa1.png
[9657c1f359d9438e9b36bf31c09a76bd.png]: https://img-blog.csdnimg.cn/9657c1f359d9438e9b36bf31c09a76bd.png
[257afd6adaa749eaa415b5e7b19321f5.png]: https://img-blog.csdnimg.cn/257afd6adaa749eaa415b5e7b19321f5.png
[30167d20cc704bedabf079fe8d8bfc8a.png]: https://img-blog.csdnimg.cn/30167d20cc704bedabf079fe8d8bfc8a.png
[69b4caca92db4246b31deb14251c4a3c.png]: https://img-blog.csdnimg.cn/69b4caca92db4246b31deb14251c4a3c.png
[28dc5ae4251c43c79a5ff8746096a8c5.gif]: https://img-blog.csdnimg.cn/28dc5ae4251c43c79a5ff8746096a8c5.gif