【初阶数据结构】堆排序和TopK问题

我不是女神ヾ 2024-04-07 10:38 29阅读 0赞

> ## 综述： ##
> 
> 1.  堆排序：排序算法，时间复杂度O(NlogN)
> 2.  TopK问题：一堆数据前K大或前K小

**目录**

综述：

1.堆的基本结构

2.堆的插入删除

2-1用数组下标计算父子关系：

2-2堆上插入元素-向上调整算法

2-3删除堆顶元素-向下调整算法

2-4完整代码

3.两种方法建堆:

3-1向上调整法建堆

3-2向下调整法建堆

3-3.完整代码

3-4.两种建堆方式的时间复杂度

4.堆排序

5.TopK问题

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

## 1.堆的基本结构 ##

> 数据结构的堆和我们在操作系统里的堆不同，我们要讲的堆就是数据结构的堆。

> 堆的逻辑结构（完全二叉树）和物理结构（数组）

![ca0718c1a5af4f39b41181d105e3ae4f.png][]

> 这里的堆是一个小根堆，（堆只分为大根堆和小根堆）  
> ps:小根堆： 堆的逻辑结构（完全二叉树中）的任意一个结点值必须大于他的左孩子和右孩子的结点值,大根堆同理。
> 
> 值得注意的是这里即使是小根堆但依然不是有序的，通过小根堆我们能直接获取到的是最小值。
> 
> PS：大小堆都只是父子之间的大小关系，兄弟之间是没有大小关系的  
> 所以下面让我们看看如何对堆进行排序。

堆只有大根堆和小跟堆，

## 2.堆的插入删除 ##

> 堆的核心就是插入数据和删除数据

### 2-1用数组下标计算父子关系： ###

> leftchild=2\*parent+1;
> 
> rightchild=2\*parent+2;
> 
> parent=(child-1)/2; 
> 
> 我用下图理解了上面的child不分leftchild和rightchild的原因。（看不懂可以按自己的方式理解）

![04a9516e56d849aaa7ed677dd88549f2.png][]

### 2-2堆上插入元素-向上调整算法 ###

> 如果在小根堆上插入一个数据，由于堆的物理结构是数组，我们采用顺序表实现，同时，如果只是简单的在数组的最后面插入一个数据，这是相当简单的，但是我们为了在插入新数据后能够继续保持堆的形态，我们通常在插入一个新数据后采用向上调整算法来实现。

> 向上调整法使用前提：树本身就是大堆或者小堆  
> 时间复杂度：LogN

#### ![d8a1db832d2c43179705c9ad468b4ba9.png][] ####

> 纠正上图：应该是向上调整算法，下图是向上调整法的图解实现

> 你是否有一个问题就是为什么在将12向上调整的时候，只用关心12的祖先的大小关系  
> 在换的过程中不会打乱除了祖先外的结点和祖先结点的大小关系吗？  
> 答案：不会，因为这本来就是小根堆，如果某结点要下移来交换，移下来的结点换下来之后一定比最原先在换下来的那个位置的结点值还更小，所以一定能够保证换下来之后不会造成父子关系乱掉。

![18a43db60d6c4b90b6fba3cfb731dfd2.png][]

####  ####

> 那么向上调整法的代码实现是什么样的呐？如下

typedef struct Heap
    {
    	int* a;
    	int size;
    	int capacity;
    }HP;
    
    void AdjustUp(int* a, int child)
    {
    	assert(a);
    	int parent = (child - 1) / 2;
    	while (child > 0)//循环里写的是继续的条件while(满足):child==0时跳出循环
    	{
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    //插入X后继续保持堆形态
    void HeapPush(HP* php, int x)
    {
    	assert(php);
    	if (php->size == php->capacity)
    	{
    		int newcapacity = 2 * php->capacity;
    		int* temp = (int*)realloc(php->a, sizeof(int) * newcapacity);
    		if (temp == NULL)
    		{
    			perror("realloc fail.\n");
    			exit(-1);
    		}
    		php->a = temp;
    		php->capacity = newcapacity;
    	}
    	php->a[php->size] = x;
    	php->size++;
    
    	//向上调整算法，传要调整的数组和从哪个下标child开始调
    	AdjustUp(php->a, php->size - 1);
    }

> HeapPush函数的内容和原来顺序表不同的是在插入新数据X后进行了向上调整，因此我们的关注点只需放在AdjustUp函数。

![ab208c5045ce4a739181424d4ee0a611.png][]

int main()
    {
    	int a[] = { 10,2,20,4,12,67,56,1 };
    	int size = sizeof(a) / sizeof(a[0]);
    	HP heap;
    	HeapInit(&heap);
    	for (int i = 0; i < size; i++)
    	{
    		HeapPush(&heap, a[i]);
        }
    	HeapPrint(&heap);
    	HeapDestory(&heap);
    	return 0;
     }

测试用例：10,2,20,4,12,67,56,1

![1262726457ca4ca5a6572024d93be77c.png][]

写成完全二叉树的形式：（预期结果：小根堆）

结果：小根堆，代码无误~~

![7db48195417b401c8ad8f11ee9115688.png][]

>  要是我想得到大根堆改如何改呐？
> 
> 小根堆就是要把小的换上去
> 
> 大根堆就是要把大的换上去
> 
> 因此同样顺序表插入代码，只需在调整部分稍作修改
> 
> 也就是只需改一下调整部分代码的判断条件

![63557fb0e80f45e790d16565411bd9fd.png][]

### 2-3删除堆顶元素-向下调整算法 ###

> 错误的顺序表式删除头：

#### ![2cf8379e8a74490ca08bc81da33e1459.png][] ####

> 正确的删除堆顶元素方式：向下调整算法  
> 前提：堆顶的把左子树和右子树都是大堆或者小堆。  
> 向下调整算法：将要删除的堆顶元素和数组的最后一个元素先做一个交换，交换后覆盖删除数组的最后一个元素，，将堆顶元素做一次向下调整。

void HeapAdjustDown(int* a, int n, int parent)
    {
    	int minchild = 2 * parent + 1;
    	while (minchild < n)
    	{
    		if (minchild + 1 < n && a[minchild] > a[minchild + 1])
    		{
    			minchild++;
    		}
    		if (a[minchild] < a[parent])
    		{
    			Swap(&a[minchild], &a[parent]);
    			parent = minchild;
    			minchild = 2 * parent + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    //删除堆顶元素，找到次小或次大的元素
    //删除之后仍要尽量保持堆的形态
    void HeapPop(HP* php)
    {
    	assert(php);
    	Swap(&php->a[0], &php->a[php->size - 1]);
    	php->size--;
    	HeapAdjustDown(php->a, php->size-1,0);
    }

![40a33a6e48c849519d4a5a69a72f9fdd.png][]

![8f8f5e5ae816497cac3671c31b6e7642.png][]

![3815b21c88a949aba7769165b5abb40c.png][]

![60fff25362e94c76b881563f0b924507.png][]

![844d05a927bf4d4b9ca4a90c1ac8fd9c.png][]

### 2-4完整代码 ###

###  ###

#include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    typedef struct Heap
    {
    	int* a;
    	int size;
    	int capacity;
    }HP;
    
    void HeapInit(HP* php)
    {
    	assert(php);
    	php->a = (int*)malloc(sizeof(HP) * 4);
    	php->size = 0;
    	php->capacity = 4;
    }
    
    void HeapDestory(HP* php)
    {
    	assert(php);
    	php->a = NULL;
    	php->size = php->capacity = 0;
    }
    
    void Swap(int* a, int* b)
    {
    	int temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    void AdjustUp(int* a, int child)
    { 
    	assert(a);
    	int parent = (child - 1) / 2;
    	while (child > 0)
    	{
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    //插入X后继续保持堆形态
    void HeapPush(HP* php, int x)
    {
    	assert(php);
    	if (php->size == php->capacity)
    	{
    		int newcapacity = 2 * php->capacity;
    		int* temp = (int*)realloc(php->a, sizeof(int) * newcapacity);
    		if (temp == NULL)
    		{
    			perror("realloc fail.\n");
    			exit(-1);
    		}
    		php->a = temp;
    		php->capacity = newcapacity;
    	}
    	php->a[php->size] = x;
    	php->size++;
    
    	//向上调整算法，传要调整的数组和从哪个下标child开始调
    	AdjustUp(php->a, php->size - 1);
    }
    
    void HeapAdjustDown(int* a, int n, int parent)
    {
    	int minchild = 2 * parent + 1;
    	while (minchild < n)
    	{
    		if (minchild + 1 < n && a[minchild] > a[minchild + 1])
    		{
    			minchild++;
    		}
    		if (a[minchild] < a[parent])
    		{
    			Swap(&a[minchild], &a[parent]);
    			parent = minchild;
    			minchild = 2 * parent + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    
    //删除堆顶元素，找到次小或次大的元素
    //删除之后仍要尽量保持堆的形态
    void HeapPop(HP* php)
    {
    	assert(php);
    	Swap(&php->a[0], &php->a[php->size - 1]);
    	php->size--;
    	HeapAdjustDown(php->a, php->size-1,0);
    }
    
    bool HeapEmpty(HP* php);
    int HeapTop(HP* php)
    {
    	assert(php);
    	assert(!HeapEmpty(php));
    	return php->a[0];
    }
    
    bool HeapEmpty(HP* php)
    {
    	assert(php);
    	return php->size == 0;
    }
    
    int HeapSize(HP* php)
    {
    	assert(php);
    	return php->size;
    }
    
    void HeapPrint(HP* php)
    {
    	assert(php);
    	for (int i = 0; i < php->size; i++)
    	{
    		printf("%d  ", php->a[i]);
    	}
    }
    
    int main()
    {
    	int a[] = { 10,2,20,4,12,67,56,1 };
    	int size = sizeof(a) / sizeof(a[0]);
    	HP heap;
    	HeapInit(&heap);
    	for (int i = 0; i < size; i++)
    	{
    		HeapPush(&heap, a[i]);
        }
    	HeapPop(&heap);
    	HeapPrint(&heap);
    	HeapDestory(&heap);
    	return 0;
     }

## 3.两种方法建堆: ##

> 从上面我们可以知道：我们已经学会了建堆以及堆的插入删除数据。  
> 但是我们知道我们建好的堆并不是有序的，而且堆中的数组和待的数组还不是同一个数组，这就意味着如果要使待排序的数组有序的话，还得将堆中的数据通过heapTop函数和HeapPop函数不断先取出堆顶元素插入到待排序数组，后删除堆顶元素（向下调整法）....![739683730a58417cb60b744691b92989.png][]

最重要的话这样的话还会导致我们使用额外的空间来拷贝待排序的数组来建堆

> **因此问题来了：怎么将数组本身建立成一个堆，从而减少额外空间的开辟  
> 如果随便给你一个数组,元素向后顺序随机,要你把这个数组建成一个小根堆.**(比如 14, 12, 4, 3, 6, 68, 21, 2 )

### 3-1向上调整法建堆 ###

> 向上调整法的使用前提:每插入一个元素前,原数组的逻辑二叉树必须是一个小根堆(大根堆).

那么我们可以把14默认为是一个符合前提的堆,然后从12往后不断向数组中插入元素,并不断向上调整,直至把整个数组元素全部插完,即完成堆的建立.

![27ce2ac54f2c487d8700bf97dac5da96.png][]

//向上调整法建堆
    	for (int i = 0; i < n; i++)
    	{
    		AdjustUp(a, i);
    	}

![8238af5cd7514a88a15daa17be1d299e.png][]

### 3-2向下调整法建堆 ###

> 向下调整法使用的前提:左子树和右子树必须是小根堆(大根堆)

由于排序的数组是随机给的,所以对于堆顶元素来说,其左子树和右子树大大部分都不是小根堆(大根堆),所以不能从第一个数组元素(堆顶)开始向下调整;同时,叶子节点不需要向下调整,所以我们采用从倒数第一个非叶子节点开始向下调整(当然如果代码中写的是从叶子节点开始向下调整,结果也没有问题,但是就是多次一举而已);

![06f02004b2984c65b7f98db5eb314dc2.png][]

向下调整法建堆
    	//for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	//{
    	//	HeapAdjustDown(a, n, i);
    	//}

![d3629909ba8a4aea8cbade0bedbfcbd8.png][]

### 3-3.完整代码 ###

void HeapSort(int* a, int n)
    {
    	//向上调整法建堆
    	for (int i = 0; i < n; i++)
    	{
    		AdjustUp(a, i);
    	}
    	
    	向下调整法建堆
    	//for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	//{
    	//	HeapAdjustDown(a, n, i);
    	//}
    }
    
    void HeapPrint2(int* a, int n)
    {
    	assert(a);
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d  ", a[i]);
    	}
    }
    
    
    
    int main()
    {
    	int a[]={ 14, 12, 4, 3, 6, 68, 21, 2 };
    	int sz = sizeof(a) / sizeof(a[0]);
    	HeapSort(a, sz);
    	HeapPrint2(a, sz);
    
    	return 0;
    }

### 3-4.两种建堆方式的时间复杂度 ###

时间复杂度=总调整次数=每一层节点个数*该层需要调整的次数

> 向下调整法建堆:LogN

![ca16e46141f4419c94d6ccfeb148d8cd.png][]

![0936bbed83a744ab9d2988c1edd2f0e5.png][]

![57caff74061a4b3f81ba27379d102044.png][]

> 向上调整法建立堆:NLogN

![a92cce2b6e5943e79d30b22249d54125.png][]

> 分析向上调整法和向下调整法建堆时间复杂度相差这么大的原因:

因为向下调整法的节点数量多的时候,需要调整的次数就少;

而向上调整法的节点数量多的时候,需要调整的次数也越多;

## 4.堆排序 ##

> 前面我们学会了如何去高效的建立堆,其中我们优先采用时间复杂度更小的向下调整法建堆

我们直接在数组上建立了堆,那我们就可以接着通过选数,把数组进行排序,从而完成堆排序

> 那么问题又来了:如果我要排升序,我们应该建大堆还是小堆呐?
> 
> 让我们想一想,如果要排升序,如果我们建立的是小堆的话,我们的确可以轻松的选出最小的数,但是如果我们在选次小的数的时候,就不得不破坏整个堆的结构,父子关系全乱了(和堆的插入和删除那里一样),这样下来重新建堆的话就是O(N)的时间复杂度;要选N个数,选一次数就要重新建一次堆的话,时间复杂度总体上就是O(N\*N),那还不如直接遍历数组n次,也是N方,这样简直是拿着一手好牌,却打的稀烂!
> 
> 所以我们升序的话采用建大堆的方式,那又有一个问题,建大堆后又是如何选出次小的呐?请往下看~~

![4e467c9e79344450a341fd9cb2311894.png][]

代码如下:(在原来的基础上增加的选数的代码完成堆排序)

void HeapSort(int* a, int n)
    {
    
    	//向下调整法建堆,时间复杂度:O(N)
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		HeapAdjustDown(a, n, i);
    	}
    
    	//升序-建小堆
    	//降序-建大堆
    
    	//选数:堆排序
    	int i = 1;
    	//时间复杂度:O(NLogN)
    	while (i < n)
    	{
    		Swap(&a[0], &a[n - i]);
    		HeapAdjustDown(a, n - i, 0);
    		++i;
    	}
    }

## 5.TopK问题 ##

> 在一堆数中,我们如果要找前K个最大的数,该怎么做?
> 
> 或许你脑海里最先想到的是用快排先排序,然后直接选择前K个数据，那代价有点大.
> 
> 这里鉴于选择排序中的堆排序的选数的经验,我们考虑采用堆的选数的思想解决这个问题.
> 
> （这里因为数据量过大，担心内存空间不够大，我们选择在磁盘上存储这些数据）

![ea786488661747bf99a665354b9fb0cb.png][]

> 这时我们优先选择建小堆，我们建一个K个数的小堆，然后将后N-K个数和堆顶元素比较，如果堆顶元素小于后N-K个树数，就交换，然后向下调整，以此类推。

#include<time.h>
    
    void CreateFileName(const char* filename, int N)
    {
    	FILE* pf = fopen(filename, "w");
    	if (pf == NULL)
    	{
    		perror("fopen\n");
    		exit(-1);
    	}
    
    	//生成随机数
    	srand(time(0));
    	for (int i = 0; i < N; i++)
    	{
    		fprintf(pf, "%d ", rand() % 10000 + 1);
    	}
    
    	fclose(pf);
    	pf = NULL;
    }
    
    void PrintTopK(const char* filename, int k)
    {
    	FILE* pf = fopen(filename, "r");
    	if (pf == NULL)
    	{
    		perror("fopen\n");
    		exit(-1);
    	}
    
    	//文件读取前K个数
    	int* minHeap = (int*)malloc(sizeof(int) * k);
    	if (minHeap == NULL)
    	{
    		perror("malloc");
    		exit(-1);
    	}
    
    	for (int i = 0; i < k; i++)
    	{
    		fscanf(pf,"%d", &minHeap[i]);
    	}
    
    	//建小堆
    	for (int i = (k-1-1)/2; i>=0;--i)
    	{
    		HeapAdjustDown(minHeap, k, i);
    	}
    	
    	//后N-k个数和堆顶元素比较
    	int val = 0;
    	while (fscanf(pf, "%d", &val)!=EOF)
    	{
    		if (val > minHeap[0])
    		{
    			minHeap[0] = val;
    			HeapAdjustDown(minHeap, k, 0);
    		}
    	}
    
    	//打印出前k大的数
    	for (int i = 0; i < k; i++)
    	{
    		printf("%d ", minHeap[i]);
    	}
    
    	fclose(pf);
    	pf = NULL;
    }
    
    
    int main()
    {
    	const char* filename = "test.txt";
    	int N = 100;
    	int k = 10;
    	//给文件内随机生成N个数
    	CreateFileName(filename, N);
    	//从文件中选出N个数中前K大的几个数字，并且打印
    	PrintTopK(filename, k);
    	return 0;
    }

![59fb0d7f3d174e5ea59c205c17cbf27c.png][]

> TopK问题的时间复杂度分析：

![c04654fa24fc438e95e85299b4892098.png][]

[ca0718c1a5af4f39b41181d105e3ae4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f76052e2a5e84125b51ea9264e5747ac.png
[04a9516e56d849aaa7ed677dd88549f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/db80e3aa7edd4e4aad30b8a5ae288548.png
[d8a1db832d2c43179705c9ad468b4ba9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/837669f3840c4be8a2dc54c730067c45.png
[18a43db60d6c4b90b6fba3cfb731dfd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d79fcfd132654fbb9d77486d50d918e6.png
[ab208c5045ce4a739181424d4ee0a611.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a7a7bfe02edb4b718002cd9f5b27c9da.png
[1262726457ca4ca5a6572024d93be77c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8a5431a33aa44d6d9117aad7b4aff1ad.png
[7db48195417b401c8ad8f11ee9115688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/50d7a5bf554c4478935c4b165f923464.png
[63557fb0e80f45e790d16565411bd9fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/c3e9a0057fcb4a4a98f9d3e1de8a14be.png
[2cf8379e8a74490ca08bc81da33e1459.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3d5217ca02b8458cb0f50b89e31e85d7.png
[40a33a6e48c849519d4a5a69a72f9fdd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/aef41e947a5c4ba3bd416b274f4fb9f8.png
[8f8f5e5ae816497cac3671c31b6e7642.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/56a0960529b54371a4da4ca5cf8ee303.png
[3815b21c88a949aba7769165b5abb40c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/c4dde8627d13469d80a61cf985c3a6f1.png
[60fff25362e94c76b881563f0b924507.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4d6b90d72e0643e0babb87ebc57c9569.png
[844d05a927bf4d4b9ca4a90c1ac8fd9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7d1b1cb8082d4335ae7a7cbe45269a85.png
[739683730a58417cb60b744691b92989.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6ef7e8d105ad4eba915ae39bdddecac2.png
[27ce2ac54f2c487d8700bf97dac5da96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/33c451c7899e4341ba9ff6a2ac53b2ab.png
[8238af5cd7514a88a15daa17be1d299e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/808918a0a7874ffabf46ce29f314e9d7.png
[06f02004b2984c65b7f98db5eb314dc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8ef432330cf143acbe7143151962f614.png
[d3629909ba8a4aea8cbade0bedbfcbd8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/52f42da3ad9e4496be8eae386e8a1a84.png
[ca16e46141f4419c94d6ccfeb148d8cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/299e0fb36d2642caa99b4112284c7644.png
[0936bbed83a744ab9d2988c1edd2f0e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3391642e82f349ee82c51f7a97861f6d.png
[57caff74061a4b3f81ba27379d102044.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b64b9e01acff4f0ca5d2696ddef2c430.png
[a92cce2b6e5943e79d30b22249d54125.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/024909968d664f7189cd4bdc5c4b7048.png
[4e467c9e79344450a341fd9cb2311894.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/075eb7d3bea54d06bb740ff6a12f9cfe.png
[ea786488661747bf99a665354b9fb0cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b8b76239048043229c6b63a0640bbaa5.png
[59fb0d7f3d174e5ea59c205c17cbf27c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7fa62fa2fe1f4dea8bdfd98550d62420.png
[c04654fa24fc438e95e85299b4892098.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0488e0e0882a4ee8bb2cb415e2b793f4.png