欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先级队列------第二次修改版本

程序员文章站 2022-03-31 20:02:18
...

目录

一、概念

二、算法分析

2.1 时间复杂度

2.2 空间复杂度

三、编程

3.1 文件结构

3.2实现 

3.3  运行结果

一、概念

优先队列是一种用来维护一组元素构成的集合S的数据结构,其中每个元素都有一个键值key,元素之间的比较都是通过key来比较。优先队列包括最大优先队列和最小优先队列。

二、算法分析

基于最小优先队列进行讨论,顾名思义:出队,队头元素是最小的;入队,直接在队尾插入就可以了。

2.1 时间复杂度

优先级队列依旧是队列,队列具有的属性和操作,优先级队列也都是具有的。真正影响时间复杂度的就是入队操作和出队操作。

1  使用无序数组,那么每一次插入的时候直接在数组末尾插入即可,入队时间复杂度为O(1),如果要保证队头元素是最小的,必须先进行查找,时间复杂度是O(n),然后将最小值和队头元素进行交换后,将队头元素出队,出队的时间复杂度是O(n)

2  使用有序数组,每一次插入通过堆排序,将元素放在合适的位置(注意,入队的时候还是在队尾插入,调整是在入队完成之后),时间复杂度是log2(n)。如果想让最小值从队首出队,由于元素已经有序,队首元素本身就是最小值。注意和无序数组作比较,无序数组出队的时候并没有保证一开始队头元素就是最小的。

经过分析,利用有序数组并且采用堆排序来构建优先级队列。

2.2 空间复杂度

不管是无序数组实现还是有序数组实现,都只需要借用一个临时空间。故空间复杂度都是O(1)。

三、编程

3.1 文件结构

优先级队列------第二次修改版本文件结构

3.2实现 

头文件

//AfxStd.h

#ifndef AFXSTD_H
#define AFXSTD_H
#include<stdio.h>	//printf()
#include<assert.h>	//assert()
#include<malloc.h>	//malloc()  free()
#include<string.h>	//memset()
#include<stdlib.h>  //exit()
typedef int ElemType;
typedef int bool;	//C语言不含bool类型
#define true 1
#define false 0
#endif 

//PriorityQueue.h

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H
#include"AfxStd.h"

typedef struct Node		//复用性好,后期可以在结构体中添加成员
{
	ElemType key;	//键值
}Node, *PNode;	//PNode pointer type

typedef struct PriorityQueue
{
	PNode queue;	//节点数组
	int capacity;	//队列容量  注意和下标区分
	int cursize;	//队列当前元素个数  注意和下标区分
}PQueue,*Pointer_PQ;

void InitQueue(Pointer_PQ pq,int size);	//初始化优先级队列
void ClearQueue(Pointer_PQ pq);	//清空优先级队列
void DestroyQueue(Pointer_PQ pq);	//摧毁优先级队列	
int QueueLength(Pointer_PQ pq);	//测量队列长度
bool QueueEmpty(Pointer_PQ pq);	//判断队列空否
bool QueueFull(Pointer_PQ pq);	//判断队列满否

Node PopFront(Pointer_PQ pq);		//删除队首节点
bool PushBack(Pointer_PQ pq, Node node);	//节点入队

void Exchange(PNode p, PNode q);	
void FilterUp(Pointer_PQ pq, int start);	//向上调整,为插入节点服务	
void FilterDown(Pointer_PQ pq, int start, int end);	//向下调整,为删除节点服务

#endif 

源文件 

//AfxStd.c

#include"AfxStd.h"

//PriorityQueue.c

#include"PoriorityQueue.h"
void InitQueue(Pointer_PQ pq, int size)	//初始化优先级队列
{
	memset(pq,0,sizeof(PQueue));
	pq->capacity = size;
	pq->queue = (Node *)malloc(sizeof(Node)*pq->capacity);
	if (NULL == pq->queue)
	{
		exit(1);
	}
}
void ClearQueue(Pointer_PQ pq)	//清空优先级队列
{
	pq->cursize = 0;	//空间可以被覆盖
}
void DestroyQueue(Pointer_PQ pq)	//摧毁优先级队列
{
	free(pq->queue);
	memset(pq, 0, sizeof(PQueue));
}
int QueueLength(Pointer_PQ pq)	//测量队列长度
{
	return pq->cursize;
}
bool QueueEmpty(Pointer_PQ pq)	//判断队列空否
{
	if (QueueLength(pq) == 0)
		return true;
	else
		return false;
}
bool QueueFull(Pointer_PQ pq)	//判断队列满否
{
	if (QueueLength(pq) == pq->capacity)
		return true;
	else
		return false;
}

Node PopFront(Pointer_PQ pq)		//删除队首节点
{
	if (QueueEmpty(pq))return ;	//队列已空,无节点可以删除
	Node tmp = pq->queue[0];
	pq->queue[0] = pq->queue[pq->cursize - 1];
	pq->cursize -= 1;
	FilterDown(pq, 0, pq->cursize - 1);
	return tmp;
}
bool PushBack(Pointer_PQ pq, Node node)	//节点入队
{
	if (QueueFull(pq))return false;	//队列已满,无法入队
	pq->queue[pq->cursize] = node;
	pq->cursize += 1;
	FilterUp(pq, pq->cursize - 1);
	return true;
}

void Exchange(PNode p, PNode q)
{
	Node tmp;
	tmp = *p;
	*p = *q;
	*q = tmp;
}
void FilterUp(Pointer_PQ pq, int start)	//向上调整,为插入节点服务,将下标为start的节点执行“上浮”操作	
{
	assert(pq != NULL);	//防止对空指针进行操作
	assert(start >= 0);	//下标合法性检查
	int j = start;	//child  进行遍历的时候,j是不能取到0
	int i = (j - 1) / 2;	//parent
	Node tmp = pq->queue[j];
	while (j > 0)
	{
		if (pq->queue[i].key < tmp.key)//parent小于child,已满足最小堆的条件
			break;
		pq->queue[j] = pq->queue[i];	//父节点下沉
		j = i;
		i = (i - 1) / 2;
	}
	pq->queue[j] = tmp;		//下标j记录的是恰当的位置

}
void FilterDown(Pointer_PQ pq, int start, int end)	//向下调整,为删除节点服务。将下标为start的节点执行“下沉”操作
{
	assert(pq != NULL);	//防止对空指针进行操作
	assert(start >= 0);	//下标合法性检查,下标end放在while循环中判断
	int i = start;	//root
	int j = i * 2 + 1;	//leftchild
	Node tmp = pq->queue[0];
	while (j <= end)
	{
		if (j < end&&pq->queue[j + 1].key < pq->queue[j].key)j += 1;	//选出键值较小的节点
		if (tmp.key < pq->queue[j].key)
			break;	//已经满足最小堆的要求
		pq->queue[i] = pq->queue[j];	//孩子节点上浮
		i = j;
		j = 2 * i + 1;
	}
	pq->queue[i] = tmp;		//下标i记录的是合适位置
}

//main.c

#include"PoriorityQueue.h"
int main()
{
	ElemType ar[] = { 23,43,12,78,96,456,234,10,6 };
	int n = sizeof(ar) / sizeof(ElemType);
	Node tmp;
	int i;
	PQueue pqueue;
	InitQueue(&pqueue, n);
	for (i = 0; i < n; ++i)
	{
		tmp.key = ar[i];
		PushBack(&pqueue, tmp);
	}
	for (i = 0; i < n; ++i)
	{
		tmp = PopFront(&pqueue);
		printf("%6d", tmp.key);
	}
	DestroyQueue(&pqueue);
	return 0;
}

3.3  运行结果

优先级队列------第二次修改版本最小堆实现的优先级队列

说明:出队的时候,队头元素最小,那么依次出队,就能把无序数组升序输出了。本程序在VS2017下运行通过,是C语言程序,遵循C89的标准。

相关标签: 优先级队列