基于堆的优先队列
堆是一种特殊的树形数据结构，具有以下性质：堆是一个完全二叉树（Complete Binary Tree）。堆中的每个节点的值都必须满足堆的性质，即父节点的值必须大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。优先队列是一种特殊的队列，其中每个元素都有一个与之关联的优先级。元素的出队顺序是根据优先级确定的，具有较高优先级的元素先出队。下面是一个基于堆的优先队列的 C 语言实现，包括创建、判空、判满、插入、查找最值、删除和摧毁等操作。#include <stdio.h>#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data;
int size;
} PriorityQueue;
// 初始化优先队列
void initialize(PriorityQueue *queue) {
queue->size = 0;
}
// 判断优先队列是否为空
int isEmpty(PriorityQueue *queue) {
return queue->size == 0;
}
// 判断优先队列是否已满
int isFull(PriorityQueue *queue) {
return queue->size == MAX_SIZE;
}
// 插入元素到优先队列
void insert(PriorityQueue *queue, int item) {
if (isFull(queue)) {
printf("Priority Queue is full. Cannot insert element.\n");
return;
}
// 将元素插入到队尾
queue->data = item;
queue->size++;
// 对插入的元素进行上浮操作，以维护堆的性质
int i = queue->size - 1;
while (i > 0 && queue->data > queue->data[(i - 1) / 2]) {
int parent = (i - 1) / 2;
int temp = queue->data;
queue->data = queue->data;
queue->data = temp;
i = parent;
}
}
// 查找优先队列中的最大值（最大堆）或最小值（最小堆）
int findMax(PriorityQueue *queue) {
if (isEmpty(queue)) {
printf("Priority Queue is empty.\n");
return -1;
}
return queue->data;
}
// 删除优先队列中的最大值（最大堆）或最小值（最小堆）
void deleteMax(PriorityQueue *queue) {
if (isEmpty(queue)) {
printf("Priority Queue is empty. Cannot delete element.\n");
return;
}
// 将堆顶元素与队尾元素交换
queue->data = queue->data;
queue->size--;
// 对交换后的堆顶元素进行下沉操作，以维护堆的性质
int i = 0;
while (1) {
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
int largest = i;
if (leftChild < queue->size && queue->data > queue->data) {
largest = leftChild;
}
if (rightChild < queue->size && queue->data > queue->data) {
largest = rightChild;
}
if (largest != i) {
int temp = queue->data;
queue->data = queue->data;
queue->data = temp;
i = largest;
} else {
break;
}
}
}
// 销毁优先队列
void destroy(PriorityQueue *queue) {
queue->size = 0;
}
int main() {
PriorityQueue queue;
initialize(&queue);
// 插入元素到优先队列
insert(&queue, 10);
insert(&queue, 30);
insert(&queue, 20);
// 输出优先队列中的最大值
printf("Max value: %d\n", findMax(&queue));
// 删除优先队列中的最大值
deleteMax(&queue);
// 输出优先队列中的最大值
printf("Max value: %d\n", findMax(&queue));
// 销毁优先队列
destroy(&queue);
return 0;
}
这段代码实现了一个最大堆的优先队列。可以根据需要修改代码中的 MAX_SIZE 宏定义来调整队列的最大容量。在 main 函数中，我们先初始化一个优先队列 queue，然后插入一些元素，查找并输出最大值，删除最大值，最后销毁队列。 堆是一种特殊的树形数据结构，具有以下性质：堆是一个完全二叉树（Complete Binary Tree）。
页:
[1]