优先队列PriorityQueue C语言实现

优先队列PriorityQueue C语言实现

基础知识

  • 堆
    堆是用数组实现的二叉树，它的逻辑结构是二叉树，存储结构是数组，所以它没有左右孩子指针。
    堆(优先队列)的结构体定义为：
#define Type int 
typedef struct HeapStruct{
	int capacity; 
	int size;
	Type *eles; 
}PriorityQueue;

堆的存储结构
capacity是堆的最大容量，创建时进行初始化；size是已使用的容量；eles是指针，用于对数据进行操作.

  • 优先队列
    优先队列是利用堆的性质实现的，分两种情况，大顶堆和小顶堆。以大顶堆为例，其性质是：

    1. 节点的左右孩子的值，都小于该节点的值
    2. 左右孩子也都是大顶堆.

    根据优先队列的性质可以看到，大顶堆的根节点即为序列的最大值，相应的小顶堆的根节点就是序列的最小值。那么我们将一组数输入到大顶堆中，然后依次输出根节点，便实现了堆排序，这样的堆就是常用的优先队列（PriorityQueue）。
    这个过程中，我们主要做的是，每插入一个元素，都要将堆调整为优先队列，同样，每删除一个根节点，也要将堆重新调整。

构建优先队列

优先队列的操作包括：

  1. 创建/初始化
  2. 判空/判满
  3. 插入
  4. 查找最值
  5. 删除
  6. 摧毁

创建

创建一个PriorityQueue结构体，并分配相应的内存，为指针eles分配capacity+1的内存。因为用数组来存储二叉树，父节点和子节点存储位置的关系是son = father/2，在插入操作中，从叶节点创建一个空穴，不断和父节点比较并上移，所以从子节点到父节点经常要取半i/2，为了操作方便，我们把数组的0号位置空出来不使用，将根节点放在i=1的位置上，因此在初始化时，分配capacity+1的内存。

PriorityQueue *init(int max_size){ //这里初始化init定义为指针函数，其返回值是指针，可以直接赋值给*pq 
	PriorityQueue *pq = NULL; //pq为结构体指针
	//检查输入大小的合法性 
	if(max_size <= 0){
		printf("max_size is illeagel!\n");
		return NULL;		
	} 
	pq = malloc(sizeof(PriorityQueue));
	
	if(pq == NULL){
		printf("malloc failed!\n");
		return NULL;
	}
	//下标为0的位置保留，不使用 
	pq->eles = malloc((max_size+1)*sizeof(Type));//为数组eles分配max_size + 1的内存
	if(pq->eles == NULL){
		printf("eles malloc failed!\n");
		free(pq);
		return NULL;
	}
	
	//初始化队列成员
	memset(pq->eles, 0, (max_size+1)*sizeof(Type));
	pq->capacity = max_size;
	pq->size = 0;
	 
	return pq;
}

在使用时只需要

PriorityQueue *pq = init(max_size);

判空

//判断是否为空
int is_empty(PriorityQueue *pq){
	if(pq == NULL) //如果指针为空
		return 0;
	if(pq->size == 0)
		return 1;
	else
		return 0; 
}

判满

//判断是否为满
int is_full(PriorityQueue *pq){
	if(pq == NULL)
		return 0;
	if(pq->size == pq->capacity)
		return 1;
	else
		return 0;
}

插入

我们在 i = size +1 的位置创建一个空穴，要插入的值value与父节点进行比较，如果大于父节点，刚将父节点与空穴交换，此时空穴的位置到了 i/2 ，然后重复上述步骤，直到 i <= 1 或value小于父节点为止，然后将value 放入到空穴里，即完成了插入操作。
以序列3， 4，7，5，8，2 为例，令capacity = 9。

  • 插入3
    插入3
  • 插入4
    插入4
    空穴与其父节点 j/2 进行比较，即 4 > 3，所以父节点与3交换，j = j/2，因为 j = 1，所以操作终止，将4放入空穴 j = 1；size = size + 1;
    插入4
  • 插入7
    插入7
    在这里插入图片描述
    在这里插入图片描述
    以此类推。最终的结果为
    插入结果
    序列在数组中的存储并不是有序的，直接遍历不能得到有序序列，因为它在结构上是树形的，类似于二叉树的顺序存储结构。
    插入操作的完整代码如下：
int push(Type value, PriorityQueue *pq){
	int i=0;
	 
	//首先判断队列是否为满 
	if(is_full(pq)){
		printf("Queue is Full!\n");
		return 0;
	}
	printf("push %d\n", value);
	
	//将最后位置+1,作为待插入的空穴，不断将空穴与父节点比较，如果比父节点大，则空穴上移 
	for(i = pq->size+1; value > pq->eles[i/2] && i>1; i/=2){
		pq->eles[i] = pq->eles[i/2];
	} 
	pq->eles[i] = value; //将value放到最后的空穴中 
	pq->size ++;
	return 1;	
}

查找最值

最值即为根节点 eles[1]，将其值赋值给value，并返回1，否则返回0；

//查找最值 
int find_max(PriorityQueue *pq, Type *value){
	if(is_empty(pq)){
		printf("Queue is empty\n");
		return 0;
	}
	*value = pq->eles[1];
	return 1;
}

删除

优先队列的删除从根节点，即eles[1]开始，每完成一次删除，将队列重新调整为优先队列。
首先将根节点赋值给max，并输出（用来实现排序）；
然后将最后一个元素取出来，赋值给last，令size - 1；如果size = 0, 则结束；
否则将根节点作为空穴，并下移。即找到空穴左右孩子中较大的值，和空穴作交换，直到空穴没有左右孩子，最后将last 放入到最后的空穴位置。
以删除8为例：将 8 赋值给max; 将最后一个值 2 取出来赋值给 last， size = size - 1;
在这里插入图片描述
移动7之后，空穴到了 i = 2的位置，其左右孩子分别在 4, 5 位置，仍将较大的孩子移动到空穴，同时空穴下移：
在这里插入图片描述
最后将 2 放入空穴：
在这里插入图片描述
完整代码如下：

//删除 
int pop(PriorityQueue *pq, Type *max){
	int i=1;
	int maxchild = 0;
	
	//判断是否为空 
	if(is_empty(pq)){
		printf("Queue is empty!\n");
		return 0;
	}
	//先把最后一个元素取出来 
	Type last;
	last = pq->eles[pq->size];
	
	//取得最大值 
	*max = pq->eles[1];
	printf("Pop %d\n", pq->eles[1]);
	pq->size --;
	if(pq->size == 0){ //如果只有一个元素
		pq->eles[i] = 0; //删除之后变为0 
		return 1;	
	}
	
	//将第一个元素作为空穴，并不断下移 
	for(i=1; i * 2 < pq->size; i = maxchild){
		maxchild = i * 2;
		//选择两个孩子中的最大值 
		if(pq->eles[maxchild] < pq->eles[maxchild+1] && maxchild != pq->size)
			maxchild += 1;
		
		//如果last比空穴处的元素小，则空穴还要往下
		if(last < pq->eles[maxchild])	
			pq->eles[i] = pq->eles[maxchild];
		else
			break;
	} 
	pq->eles[i] = last;
	return 1;	 
}

摧毁

int destroy(PriorityQueue *pq) {
	if(pq == NULL){
		return 0;
	}
	free(pq->eles);
	pq->eles = NULL;
	free(pq);
	pq = NULL;
	
	printf("destroy success\n");
	return 1;
}
  • 测试
int main(void){
	//创建容量为6的优先队列 
	PriorityQueue *pq = init(6); //init在定义时，定义为指针，因此其返回值是个指针，直接复制给pq 
	
	int arr[]={3,4,7,5,8,2,9,10} ;
	int i = 0;
	
	//试图插入多于6个的元素，最后两个元素将无法插入 
	for(i = 0; i<8; i++){
		push(arr[i], pq);
	} 
	
	//遍历队列内容
	printf("the value of pq are: ") ;
	for(i=0; i<pq->size; i++){
		printf("%d ", pq->eles[i+1]); 
	}
	printf("\n");
	printf("pq size is %d\n", pq->size);
	
	Type max;
	int size = pq->size;
	//每次从堆顶取元素
	for(i=0; i<size; i++){
		if(find_max(pq, &max)){
			printf("the max is %d\n", max);
			pop(pq, &max);
		}	
	}
	printf("new size is %d\n", pq->size) ;
	
	//销毁队列 
	destroy(pq);
	
	return 0;
}
  • 输出
    在这里插入图片描述
    完整可运行代码：
//大顶堆
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Type int 

/*定义优先队列的数据结构*/ 
typedef struct HeapStruct{
	int capacity; //最大容量 
	int size;
	Type *eles; 
}PriorityQueue;

//初始化优先队列 ,创建空堆，初始化元素为0 
PriorityQueue *init(int max_size){  //这里初始化init定义为指针函数，其返回值是指针，可以直接赋值给*pq 
	PriorityQueue *pq = NULL;
	
	//检查输入大小的合法性 
	if(max_size <= 0){
		printf("max_size is illeagel!\n");
		return NULL;		
	} 
	pq = malloc(sizeof(PriorityQueue));
	
	if(pq == NULL){
		printf("malloc failed!\n");
		return NULL;
	}
	//下标为0的位置保留，不使用 
	pq->eles = malloc((max_size+1)*sizeof(Type));
	if(pq->eles == NULL){
		printf("eles malloc failed!\n");
		free(pq);
		return NULL;
	}
	
	//初始化队列成员
	memset(pq->eles, 0, (max_size+1)*sizeof(Type));
	pq->capacity = max_size;
	pq->size = 0;
	 
	return pq;
}

//判断是否为空 
int is_empty(PriorityQueue *pq){
	if(pq == NULL)
		return 0;
	if(pq->size == 0)
		return 1;
	else
		return 0; 
}

//判断是否为满
int is_full(PriorityQueue *pq){
	if(pq == NULL)
		return 0;
	if(pq->size == pq->capacity)
		return 1;
	else
		return 0;
}

//插入
int push(Type value, PriorityQueue *pq){
	int i=0;
	 
	//首先判断队列是否为满 
	if(is_full(pq)){
		printf("Queue is Full!\n");
		return 0;
	}
	printf("push %d\n", value);
	
	//将最后位置+1,作为待插入的空穴，不断将空穴与父节点比较，如果比父节点大，则空穴上移 
	for(i = pq->size+1; value > pq->eles[i/2] && i>1; i/=2){
		pq->eles[i] = pq->eles[i/2];
	} 
	pq->eles[i] = value; //将value放到最后的空穴中 
	pq->size ++;
	return 1;	
}
//查找最值 
int find_max(PriorityQueue *pq, Type *value){
	if(is_empty(pq)){
		printf("Queue is empty\n");
		return 0;
	}
	*value = pq->eles[1];
	return 1;
}

//删除 
int pop(PriorityQueue *pq, Type *max){
	int i=1;
	int maxchild = 0;
	
	//判断是否为空 
	if(is_empty(pq)){
		printf("Queue is empty!\n");
		return 0;
	}
	//先把最后一个元素取出来 
	Type last;
	last = pq->eles[pq->size];
	
	//取得最大值 
	*max = pq->eles[1];
	printf("Pop %d\n", pq->eles[1]);
	pq->size --;
	if(pq->size == 0){ //如果只有一个元素
		pq->eles[i] = 0; //删除之后变为0 
		return 1;	
	}
	
	//将第一个元素作为空穴，并不断下移 
	for(i=1; i * 2 < pq->size; i = maxchild){
		maxchild = i * 2;
		//选择两个孩子中的最大值 
		if(pq->eles[maxchild] < pq->eles[maxchild+1] && maxchild != pq->size)
			maxchild += 1;
		
		//如果last比空穴处的元素小，则空穴还要往下
		if(last < pq->eles[maxchild])	
			pq->eles[i] = pq->eles[maxchild];
		else
			break;
	} 
	pq->eles[i] = last;
	return 1;	 
} 
//摧毁
int destroy(PriorityQueue *pq) {
	if(pq == NULL){
		return 0;
	}
	free(pq->eles);
	pq->eles = NULL;
	free(pq);
	pq = NULL;
	
	printf("destroy success\n");
	return 1;
}
//测试
int main(void){
	//创建容量为6的优先队列 
	PriorityQueue *pq = init(6); //init在定义时，定义为指针，因此其返回值是个指针，直接复制给pq 
	
	int arr[]={3,4,7,5,8,2,9,10} ;
	int i = 0;
	
	//试图插入多于6个的元素，最后两个元素将无法插入 
	for(i = 0; i<8; i++){
		push(arr[i], pq);
	} 
	
	//遍历队列内容
	printf("the value of pq are: ") ;
	for(i=0; i<pq->size; i++){
		printf("%d ", pq->eles[i+1]); 
	}
	printf("\n");
	printf("pq size is %d\n", pq->size);
	
	Type max;
	int size = pq->size;
	//每次从堆顶取元素
	for(i=0; i<size; i++){
		if(find_max(pq, &max)){
			printf("the max is %d\n", max);
			pop(pq, &max);
		}	
	}
	printf("new size is %d\n", pq->size) ;
	
	//销毁队列 
	destroy(pq);
	
	return 0;
}
  • 欢迎讨论
版权声明：本文为Sungree原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。