优先级队列------第二次修改版本
程序员文章站
2022-03-31 20:02:18
...
目录
一、概念
优先队列是一种用来维护一组元素构成的集合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的标准。
上一篇： 如何制作并使用ico图标呢？