用堆实现优先级队列

时间:2022-08-22 10:14:15

申明:要用到堆的基本操作代码,链接为:https://blog.csdn.net/ijn842/article/details/80299647


优先队列是一种数据结构,能够保证每次出队的是队列中优先级最高的元素,使用堆的堆顶元素维护这个优先级最高的元素,因为堆具有堆序性,堆顶元素要么是最小的,要么是最大的。

PriorityQueue.h

typedef struct PriorityQueue 
{ 
	Heap* _hp; 
}PriorityQueue; 

// 优先级队列初始化 
void PriorityQueueInit(PriorityQueue* q, Compare com); 

// 向队列中插入元素 
void PriorityQueuePush(PriorityQueue* q, DataType data); 

// 删除优先级最高的元素 
void PriorityQueuePop(PriorityQueue* q); 

// 获取队列中元素个数 
int PriorityQueueSize(PriorityQueue* q); 

// 检测优先级队列是否为空 
int PriorityQueueEmpty(PriorityQueue* q); 

// 获取堆顶的元素 
DataType PriorityQueueTop(PriorityQueue* q); 

// 销毁优先级队列 
void PriorityQueueDestroy(PriorityQueue* q); 

PriorityQueue.c

// 优先级队列初始化 
void PriorityQueueInit(PriorityQueue* q, Compare com)
{
	HeapInit(q->_hp,com);
}

// 向队列中插入元素 
void PriorityQueuePush(PriorityQueue* q, DataType data)
{
	HeapInsert(q->_hp,data);
}

// 删除优先级最高的元素 
void PriorityQueuePop(PriorityQueue* q)
{
	DestoryHeap(q->_hp);
}

// 查看队列元素个数
int PriorityQueueSize(PriorityQueue* q)
{
	return HeapSize(q->_hp);
}

// 检测优先级队列是否为空 
int PriorityQueueEmpty(PriorityQueue* q)
{
	return HeapEmpty(q->_hp);
}

// 获取堆顶的元素 
DataType PriorityQueueTop(PriorityQueue* q)
{
	return HeapTop(q->_hp);
}

// 销毁优先级队列 
void PriorityQueueDestroy(PriorityQueue* q)
{
    DestoryHeap(q->_hp);
}

test.c

#include "Heap.h"

int main()
{
	PriorityQueue q;
	PriorityQueueInit(&q,Less);
	PriorityQueuePush(&q,8);
	PriorityQueuePush(&q,2);
	PriorityQueuePush(&q,5);
	PriorityQueuePush(&q,4);
	PriorityQueuePush(&q,7);
	PriorityQueuePush(&q,9);
	PriorityQueuePush(&q,3);
	DataType top = QueueTop(&q);
    int size = QueueSize(&q);
    int ret = QueueEmpty(&q);

    QueuePop(&q);
    QueuePop(&q);

    top = QueueTop(&q);
    size = QueueSize(&q);
    ret = QueueEmpty(&q);
	return 0;
}