写给自家娃看的算法书----堆排序，C语言实现

古城微笑少年丶 2023-03-02 10:51 6阅读 0赞

选择排序时，采用遍历的方式在n个元素中找最大 (小) 的元素，时间复杂度是O(N)，这是一个非常慢的操作。如果把这个操作的时间复杂度降低到O(logN)，排序速度就会明显变快。这就是选择排序的高级形式：堆排序。下面我们从堆的前世今生开始讲。  
在前面我们已经学过完全二叉树了，我们在完全二叉树的基础上提出“大顶堆”和“小顶堆”的概念。这里我们主要讨论“大顶堆”：“大顶堆”是一棵完全二叉树，而且堆顶元素一定比两个儿子 (如果存在的话) 都大 (或相等)，但是两个儿子之间没有大小的要求。例如下图中A图是一个大顶堆，B图不是完全二叉树、C图中有一个子树不符合大顶堆的定义，所以B图和C图不是大顶堆。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
有了大顶堆的定义之后，我们想知道它有什么用。  
可以看到：大顶堆中堆顶元素是整个堆中最大的元素，如果把堆顶元素去掉，并且把最后一个元素放到堆顶，我们最多只需要进行logN次 (N个元素的堆一共有 logN + 1层，简化后记作logN) 调整，就可以让所有元素重新符合大顶堆的定义，新堆的元素个数比原来少1。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]  
用“堆”的方式寻找最大 (小) 值的时间复杂度为O(logN)，把这种利用“堆”寻找最小 (大) 值的方式用在选择排序中，那么选择排序的效率就可以从O(N2) 提高到O(N \* logN)。这种改进方式就是堆排序。要实现堆排序，我们需要解决下面几个问题：  
1、堆的存储方式。  
由于堆是一棵完全二叉树，可以用一维数组储存，所有元素都是挨在一起的，中间没有空位，这种储存方式非常紧凑，不浪费空间。遍历这个一维数组就是用层序方式遍历堆。  
2、怎么建大顶堆？  
建大顶堆有两种方式：① 从一个空的堆开始，一个一个增加数据，直到所有数据都添加完成。这种方式每增加一个数据都要进行O(logN)次调整，所以建堆的时间复杂度为O(N \* logN)；② 直接对所有的数据进行调整得到堆，这种建堆的时间复杂度为O(N)。显然第二种方式建堆更快。在本章中，我们只讨论第二种方式。第一种方式在优先级队列中很有用，优先级队列的内容我们将在扩展篇中讨论。

大顶堆的定义要求：堆顶元素一定比两个儿子 (如果存在的话) 都大 (或相等)。如果堆顶元素的编号是i，那么它的左儿子的编号是2 \* i + 1，右儿子的编号是2 \* i + 2 (如果存在的话)。接下来，我们就只需要在这三个元素中找到最大值即可，可以用一个getMaxIndex()函数实现这个功能：

三个参数分别是是father和两个儿子的编号。father一定存在，但两个儿子不一定存在。

int getMaxIndex(int father, int leftSon, int rightSon)
    {
        
    	int maxIndex = father; //默认father是最大值的编号
    	//注意，if语句中的两个条件的次序不能反着写哦。
    	if(leftSon < size && arr[maxIndex] < arr[leftSon]) //leftSon < size表示左儿子存在
    	{
        
    		maxIndex = leftSon; //更新最大值的编号
    	}
    	if(rightSon < size && arr[maxIndex] < arr[rightSon]) //rightSon < size表示右儿子存在
    	{
        
    		maxIndex = rightSon; //更新最大值的编号
    	}
    	return maxIndex; //返回最大值的编号
    }

找到这个最大值之后，需要跟父节点比较一下，如果父节点本来就是最大值，那就说明这三个数符合大顶堆的要求，就不需要调整了。否则就需要调整。怎么调整？很简单，就是把最大的那个值跟父节点交换一下即可:

swap(father, maxIndex)；

但是以maxIndex这个结点作为子堆的堆顶元素之后，子堆可能又不符合要求了，那就继续用相同的方式调整吧。看到“相同的方式”这几个字，我们自然而然的想到了用递归：

void shiftDown(int i) //向下调整。i是父节点的编号
    {
        
    	//找到father、两个儿子中的最大值 
    	int maxIndex = getMaxIndex(i, i * 2 + 1, i * 2 + 2);
    	
    	//如果father不是最大的值 (也就是说不符合堆的定义)，需要要调整
    	//把编号为maxIndex的那个值与father进行交换 
    	if(maxIndex != i)
    	{
        
    		swap(maxIndex, i); //交换 
    		shiftDown(maxIndex); //递归调整子堆
    	}
    	//如果father是最大的值，符合堆的定义，退出递归 
    	else //递归的出口
    	{
        
    		return;
    	}
    }

也可以用迭代的方式进行维护，这样就可以避免递归造成的一些问题：

void shiftDown(int i) //向下调整。i是父节点的编号
    {
        
    	int maxIndex = 0; 
    	while(true)
    	{
        
    		//找到father、两个儿子中的最大值
    		maxIndex = getMaxIndex(i, i * 2 + 1, i * 2 + 2);
    	
    		//如果father不是最大的值 (也就是说不符合堆的定义)，需要要调整
    		//把编号为maxIndex的那个值与father进行交换  
    		if(maxIndex != i)
    		{
        
    			swap(maxIndex, i); //交换  
    			i = maxIndex; //更新i的编号，继续下一轮循环
    		}
    		else //符合堆的定义时，退出循环 
    		{
        
    			break;
    		}
    	}
    }

我们要想一想从哪里开始维护堆？对于叶子结点而言，它没有子节点，所以没有必要对叶子结点进行维护。最后一个有子节点的元素的编号是 (n - 1) / 2。我们可以从最后一个有子节点的元素开始维护，反着进行，第一个元素最后维护。部分资料中，是从数组编号为1的位置开始存放数据的，这时最后一个有子节点的元素的编号是n / 2。为了兼容这种方式，我们也从编号为n / 2的元素开始维护。这样做可能会多维护一次，但不影响结果。

for(int i = size / 2; i >= 0; i--)
    {
        
    	shiftDown(i);
    }

3、我们已经能建立大顶堆了，也知道怎么维护堆了。也知道首元素 (堆顶元素) 是最大值了，接下来怎么进行堆排序呢？  
在完成上面的准备工作之后，我们只需要把堆顶元素与最后的元素进行交换，然后从堆顶开始重新维护这个大顶堆，同时size–，避免下一次把最大的元素放进堆中进行调整。这样，随着size逐渐变小，堆也逐渐变小，每次找到的最大值也变小。最后得到一个从小到大排序的数组。这就是堆排序。

下面是堆排序的完整代码：

#include <stdio.h> 
    #include <stdlib.h>
    
    int arr[] = {
        4,1,5,7,3,2,9,8,6,0,5,4,3,6,7,8};
    int size = 0;
    
    int swap(int a, int b)
    {
        
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    //三个参数分别是是father和两个儿子的编号。father一定存在，但两个儿子不一定存在。 
    int getMaxIndex(int father, int leftSon, int rightSon)
    {
        
    	int maxIndex = father; //默认father是最大值的编号
    	
    	if(leftSon < size && arr[maxIndex] < arr[leftSon]) //leftSon < size表示左儿子存在
    	{
        
    		maxIndex = leftSon; //更新最大值的编号
    	}
    	if(rightSon < size && arr[maxIndex] < arr[rightSon]) //rightSon < size表示右儿子存在
    	{
        
    		maxIndex = rightSon; //更新最大值的编号
    	}
    	return maxIndex; //返回最大值的编号 
    }
    
    void shiftDown(int i) //向下调整。i是父节点的编号
    {
        
    	int maxIndex = 0; 
    	while(true)
    	{
        
    		//找到father、两个儿子中的最大值
    		maxIndex = getMaxIndex(i, i * 2 + 1, i * 2 + 2);
    	
    		//如果father不是最大的值 (也就是说不符合堆的定义)，需要要调整
    		//就是把编号为maxIndex的那个值与father进行交换  
    		if(maxIndex != i)
    		{
        
    			swap(maxIndex, i); //交换  
    			i = maxIndex; //更新i的编号，继续下一轮循环
    		}
    		else //符合堆的定义时，退出循环 
    		{
        
    			break;
    		}
    	}
    }
    
    void createMaxHeap() //建立大顶堆
    {
        
    	//最后一个有子节点的元素的编号是 (n - 1) / 2，
    	//为了兼容其它资料的储存方式，这里也从n / 2开始进行维护
    	for(int i = size / 2; i >= 0; i--)
    	{
        
    		shiftDown(i);
    	}
    } 
    
    void heapSort() //堆排序
    {
        
    	printf("size = %d\r\n", size);
    	createMaxHeap(); //建堆 
    	printf("建堆结束\r\n");
    	
    	int size2 = size; //备份size 
    	while(size > 0) //排序
    	{
        
    		//交换堆顶元素与最后一个元素。也就是把最大的元素放到最后 
    		swap(size - 1, 0); 
    		size--; //先n--，然后调整堆 
    		shiftDown(0); //堆顶元素被交换掉了。所以要从顶上开始调整堆 
    	}
    	size = size2; //恢复size
    }
    
    int main()
    {
        
    	size = sizeof(arr) / sizeof(int); //动态计算数组的大小
    	heapSort(); //堆排序 
    	return 0;
    }

下面分析一下堆排序的时间复杂度。堆排序消耗的时间分为两部分：1、建堆过程，时间复杂度为O(N)；2、排序过程：找到一个最大值后需要进行logN次调整才能使整个堆重新符合大顶堆的定义，一共n个元素，所以排序过程的时间复杂度为：O(N \* logN)。整个堆排序的时间复杂度为：O(N + N \* logN) = O(N \* logN)。正是因为堆排序中存在一个额外的建堆过程，所以相对于其它高级排序算法，堆排序是最慢的。  
值得注意的是，堆排序在任何情况下的时间复杂度都是O(N \* logN)，且它只需要1个单位的辅助空间即可完成排序。可以说是非常节约内存的一种排序方式。这个排序算法在内存非常紧张的设备 (例如52单片机只有256个字节的内存空间) 中非常有用，而且堆排序还可以进行部分排序，这也是非常特殊的能力。另外，堆排序是跳跃式交换数据的，所以它是一种不稳定的排序算法。  
堆除了用于排序之外，还有很多其它用处，比如实现优先级队列、用于优化寻找最大 (小) 值、用于寻找最大 (小) 的第k个值，或前k个值、求中值等，这些内容我们将在扩展篇中继续讨论。

下一小节，我们继续讨论堆排序的一种改进方式。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230208/6951d368f4114fdf9a7f719502db43ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230208/21ebb16a615b483e8ef3b7e5a92baeea.png