优先级队列的实现，与堆排序的对比(C语言实现)

刺骨的言语ヽ痛彻心扉 2023-03-01 05:35 3阅读 0赞

我们在第四章学习了使用数组实现的队列。这样的队列就是在tail的位置入列 (插入数据)，在head的位置出列 (删除数据)。遵循“先进先出”的原则。这里我们要介绍的“优先级队列”是用“堆”实现的。“优先级队列”不再遵循“先进先出”的规则。小顶堆实现的优先级队列遵循“优先级最低的元素最先出列”的原则，大顶堆实现的优先级队列遵循“优先级最高的元素最先出列”的原则。

堆排序与优先级队列的区别：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]下面的例子中，入列的元素大小是无序的，实现的是大顶堆。所以这个优先级队列是按照从大到小次序出列的。下面，我们就用代码实现优先级队列：

数组arrResource中存放着入列用的10个元素：

int arrResource[10] = {
        3, 4, 1, 2, 3, 6, 5, 9, 3, 8}; //入列的元素
    int priorQueue [10]; //用数组实现堆，用堆实现优先级队列 
    
    int totalNum = 10; //arrResource中一共有10个元素 
    int size = 0; //优先级队列中有0个元素 
    int dequeuedNum = 0; //已经出列的元素个数

与堆排序相比，这里一共多了四个函数：  
1、显示优先级队列中的所有元素。这个函数就是简单的遍历数组。

void showQueue() 
    {
        
    	for(int i = 0; i < size; i++)
    	{
        
    		printf("%d, ", priorQueue[i]);
    	}
    	printf("\r\n");
    }

2、优先级队列的入列。数据进入优先级队列之后可能会破坏堆，所以要重新维护堆。如果一共要入列k个元素，则现场维护堆的时间成本是O(K \* logN)，而完全重建堆的时间复杂度为O(N)。这时会有一个什么时候维护堆的问题。如果只是入列一两个元素，那就应该选择现场维护。但是如果一次性入列很多个元素，那么现场维护的时间成本O(K \* logN) 可能高于重新建堆 O(N)，所以应该选择完全重建堆。这里，我们选择现场维护的方式。

void enqueue(int n) //把元素n入列 
    {
        
    	priorQueue[size] = n; //入列 
    	size++; //优先级队列中的元素 + 1 
    	shiftUp(size - 1); //每次入列都进行维护。注意，这是向上调整
    }

3、优先级队列的出列。利用堆的方式出列：只出列堆顶元素，且在出列 (堆中的元素发生变化) 之后重新维护堆，使剩余元素符合大顶堆的要求。这样才能保证每次输出的都是最大值。

int dequeue() //优先级队列出列，得到最大值 
    {
        
    	if(size <= 0) //防止出错 
    	{
        
    		return -1; //返回-1表示出错 
    	}
    	int max = priorQueue[0]; //记录当前堆中的最大值
    	
    	//这三行就是堆排序中的一次循环
    	swap(0, size - 1); //把首元素与尾元素交换
    	size--; //堆的大小-1
    	shiftDown(0); //重新维护堆：向下调整数据
    	dequeuedNum++; //出列的元素个数++
    	 
    	return max; //返回最大值 
    }

4、优先级队列中的元素的修改。堆排序算法中不修改堆中的元素的数据。但是在优先级队列中可以修改。那么问题来了：对于一个大顶堆，如果修改之后的值比原先大，该怎么调整；如果修改之后的值比原先小，又该怎么调整呢？  
把所有数据重建堆 (完整维护堆) 当然是一个可行的方法，但是这样做的时间复杂度为O(N)。由于绝大部分数据都在正确的位置，所以不如做一次部分维护。部分维护的时间复杂度为O(logN)。因为这是一个大顶堆，所以如果修改之后的数比原先大，那么这个数就应该尽量往堆顶方向调整，也就是调用shiftUp() 函数进行部分维护；相反，如果修改之后的数比原先小，就应该调用shiftDown() 函数。

//把堆中priorQueue[index]的值修改成num。修改后要重新维护堆，采用部分维护。 
    void editNum(int index, int num)
    {
        
    	int num0 = priorQueue[index]; //记录被修改的原数据
    	priorQueue[index] = num; //修改堆中数据
    	
    	//如果修改前后的值一样，那就没必要调整。
    	if(num0 < num) //这个是大顶堆，修改后的数据比原来的数据大，所以应该向上调整 
    	{
        
    		shiftUp(index);
    	}
    	else if(num0 > num) //这个是大顶堆，修改后的数据比原来的数据小，所以应该向下调整
    	{
        
    		shiftDown(index);
    	}
    }

完整的优先级队列的实现代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int totalNum = 10; //arrResource中一共有10个元素 
    int size = 0; //优先级队列中有0个元素 
    int dequeuedNum = 0; //已经出列的元素个数
     
    //入列用的10个元素 
    int arrResource[10] = {
        3, 4, 1, 2, 3, 6, 5, 9, 3, 8};
    int priorQueue [10]; //用数组实现堆，用堆实现优先级队列 
    
    void showQueue() //依次显示优先级队列中的所有元素 
    {
        
    	for(int i = 0; i < size; i++)
    	{
        
    		printf("%d, ", priorQueue[i]);
    	}
    	printf("\r\n");
    }
    
    //求优先级队列priorQueue中的三个元素的最大值的编号
    //三个参数分别是是father和两个儿子的编号。
    //father一定存在，但两个儿子不一定存在。 
    int getMaxIndex(int father, int leftSon, int rightSon)
    {
        
    	int maxIndex = father; //默认father是最大值的编号
    	int max = priorQueue[father]; //最大值 
    	
    	//leftSon < size表示左儿子存在，且左儿子比father更大
    	if(leftSon < size && max < priorQueue[leftSon])
    	{
        
    		max = priorQueue[leftSon]; //更新最大值
    		maxIndex = leftSon; //更新最大值的编号
    	} 
    	if(rightSon < size && max < priorQueue[rightSon])
    	{
        
    		//max = priorQueue[rightSon]; //更新最大值，可以省略这个语句
    		maxIndex = rightSon; //更新最大值的编号
    	}
    	return maxIndex;
    }
    
    void swap(int a, int b) //交换优先级队列中的元素 
    {
        
    	int temp = priorQueue[a];
    	priorQueue[a] = priorQueue[b];
    	priorQueue[b] = temp;
    }
    
    //shiftDown()是部分维护堆，时间复杂度为O(logN)
    //删除元素时用shiftDown(),把数据从上往下调整  
    void shiftDown(int i) //调整以编号为i的元素以下的大顶堆 
    {
        
    	int maxIndex = 0; //记录最大值的编号 
    	while(1)
    	{
        
    		//在father和两个儿子之间找到最大值 
    		maxIndex = getMaxIndex(i, 2 * i + 1, 2 * i + 2);
    		if(maxIndex != i) //如果father不是最大值 
    		{
        
    			swap(i, maxIndex); //交换最大值和father 
    			i = maxIndex; //更新i 
    		}
    		else //如果father是最大值 
    		{
        
    			break; //退出循环 
    		}
    	}
    }
    
    //shiftUp()是部分维护堆，时间复杂度为O(logN)
    //添加元素时用shiftUp()，把最底下的元素往上调整  
    void shiftUp(int i)  
    {
        
    	int maxIndex = 0; //记录最大值的编号 
    	while(true)
    	{
        
    		//这个i一定是儿子结点，但不知道是左儿子还是右儿子 
    		//数组从0开始计数，不管i是左儿子还是右儿子，father一定是(i - 1) / 2
    		int father = (i - 1) / 2; 
    		
    		//在father和两个儿子之间找到最大值 
    		maxIndex = getMaxIndex(father, 2 * father + 1, 2 * father + 2);
    		if(maxIndex != father) //如果father不是最大值 
    		{
        
    			swap(father, maxIndex); //交换最大值和father 
    			i = father; //更新i，以便下一轮循环重新计算father的值 
    		}
    		else //如果father是最大值 
    		{
        
    			break; //退出循环 
    		}
    	}
    }
    
    //建堆：彻底的维护堆。时间复杂度为O(N)
    void createHeap()
    {
        
    	for(int i = size / 2; i >= 0; i--) //线性建堆 
    	{
        
    		shiftDown(i);
    	}
    } 
    
    void heapSort() //堆排序
    {
        
    	createHeap(); //堆排序要先建堆
    
    	int size2 = size; //备份size 
    	while(size > 0) //堆排序的时候，size会发生改变 
    	{
        
    		swap(0, size - 1); //把首元素与尾元素交换
    		size--; //堆的大小-1
    		shiftDown(0); //重新维护堆 
    	}
    	size = size2; //恢复size 
    } 
    
    void enqueue(int n) //把元素n入列 
    {
        
    	priorQueue[size] = n; //入列 
    	size++; //优先级队列中的元素 + 1 
    	shiftUp(size - 1); //每次入列都进行维护，注意，这是向上调整
    }
    
    //优先级队列出列，得到最大值。
    //出列后要重新维护堆，这样才能保证堆顶元素是最大值 
    int dequeue() 
    {
        
    	if(size <= 0) //防止出错 
    	{
        
    		return -1; //返回-1表示出错 
    	}
    	int max = priorQueue[0]; //记录当前堆中的最大值
    	
    	//这三行就是堆排序中的一次循环
    	swap(0, size - 1); //把首元素与尾元素交换
    	size--; //堆的大小-1
    	shiftDown(0); //重新维护堆：向下调整数据
    	dequeuedNum++; //出列的元素个数++
    	return max; //返回最大值 
    } 
    
    //把堆中priorQueue[index]的值修改成num。修改后要重新维护堆，采用部分维护。 
    void editNum(int index, int num)
    {
        
    	//优先级队列存放在数组中，所以可以根据index获得指定元素
    	int num0 = priorQueue[index]; //记录被修改的原数据
    	priorQueue[index] = num; //对指定元素进行赋值
    	
    	//如果修改前后的值一样，那就没必要调整。
    	if(num0 < num) //大顶堆，修改后的值比原来的值大，所以应该向上调整 
    	{
        
    		shiftUp(index);
    	}
    	else if(num0 > num) //大顶堆，修改后的值比原来的值小，所以应该向下调整
    	{
        
    		shiftDown(index);
    	}
    }
    
    int main()
    {
        
    	int result = 0;
    	 
    	for(int i = 0; i < totalNum / 2; i++) //入列一半元素 
    	{
        
    		enqueue(arrResource[i]); //入列，完成后进行部分维护堆 
    	}
    	printf("入列一半元素：");
    	showQueue();
    
    	for(int i = 0; i < 2; i++) //出列2个元素
    	{
        
    		result = dequeue(); //出列
    		printf("出列: %d；剩余元素：", result); 
    		showQueue();
    	} 
    	
    	printf("入列剩余一半元素: ");
    	for(int i = totalNum / 2; i < totalNum; i++) //入列剩余一半元素 
    	{
        
    		enqueue(arrResource[i]); //入列，完成后进行部分维护堆 
    	}
    	showQueue();
    	
    	int index = 3; 
    	int num = 10;
    	printf("修改队列中index = %d的元素为%d，然后重新维护堆: \r\n", index, num);
    	editNum(index, num);
    	showQueue();
    
    	while(dequeuedNum < totalNum) //还没有完全出列时继续循环 
    	{
        
    		result = dequeue(); //出列
    		printf("出列: %d；剩余元素：", result); 
    		showQueue();
    	}
    	
    	for(int i = 0; i < totalNum; i++) //重新入列所有元素 
    	{
        
    		enqueue(arrResource[i]); //入列
    	}
    	
    	printf("\r\n重新入列所有元素，堆排序之前: ");
    	showQueue();
    	
    	printf("堆排序之后: ");
    	heapSort();
    	showQueue();
    	
    	//重新建堆，并按照优先级队列出列 
    	createHeap();  
    	printf("\r\n出列所有元素: ");
    	dequeuedNum = 0;
    	while(dequeuedNum < totalNum) //还没有完全出列时继续循环 
    	{
        
    		result = dequeue(); //出列
    		printf("%d, ", result); 
    	}
    	
    	printf("\r\nHello\r\n"); //判断软件能正常工作的一个小技巧 
    	return 0;
    }

注意：  
1、如果一次性把所有元素都入列，然后按照优先级最大的元素先出列的原则进行出列。那么优先级队列就变成了堆排序。但这个堆排序的结果是从大到小排序的。  
2、优先级队列是可以入列和出列的。出列的结果是从大到小出列。  
3、队列中的元素发生变化之后都需要重新维护一次大顶堆，所以剩余元素的次序可能会发生变化。  
4、如果每入列一个元素，紧接着就出列。直到所有元素都入列/出列完成。这时，优先级队列就退化成栈了，输出结果就跟栈一样了。

运行结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]最后想说一下，其实队列和优先级队列没什么关系。只是名字中都包含“队列”这两个字而已。如果一定要说相似，那就是普通队列是先入列的元素先出列；而优先级队列则是优先级最高的元素最先出列，仅此而已。  
另外，既然有优先级队列，那么有没有优先级栈呢？答案是没有必要有。对于用数组实现的队列和栈而言，两者都是在数组最后添加数据，两者的区别仅仅是删除数据的位置不同罢了，优先级队列显然已经破坏了从队列头部删除数据的规则，如果有优先级栈，优先级栈的出栈位置显然也不会在数组的末尾，那么优先级队列和优先级栈就没有任何区别了。所以，没有必要存在优先级栈。

优先级队列的应用：  
如果存在一个集合，集合中会动态地添加一些数据进来，有时又会删除一个数据，有时甚至会修改集合中的某一个值。要求删除这个集合中最小的数据，请问该怎么做？  
这个问题其实就是问怎么找到一个集合中的最小值？最简单的方法是遍历所有的数据，找到最小值。这样做的时间复杂度为O(N)。如果我们用优先级队列来实现，时间复杂度是 (logN)。显然，用优先级队列的效率要高很多。事实上，改进的Dijkstra算法和Prim算法就是用优先级队列寻找最小值。下一小节我们就来看看Dijkstra算法的优化方式。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/29d1a1a68f994492af83917a9e14aca8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/90cb9ce2fd804758b33f8fe9fd45b479.png