基于堆的优先队列

1万 · 2024-11-12 13:00

堆是一种特殊的树形数据结构，具有以下性质：堆是一个完全二叉树（Complete Binary Tree）。堆中的每个节点的值都必须满足堆的性质，即父节点的值必须大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。优先队列是一种特殊的队列，其中每个元素都有一个与之关联的优先级。元素的出队顺序是根据优先级确定的，具有较高优先级的元素先出队。下面是一个基于堆的优先队列的 C 语言实现，包括创建、判空、判满、插入、查找最值、删除和摧毁等操作。#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
int data[MAX_SIZE];
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[queue->size] = 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[parent];
      queue->data[parent] = temp;
      i = parent;
}
}

// 查找优先队列中的最大值（最大堆）或最小值（最小堆）
int findMax(PriorityQueue *queue) {
if (isEmpty(queue)) {
      printf("Priority Queue is empty.\n");
      return -1;
}

return queue->data[0];
}

// 删除优先队列中的最大值（最大堆）或最小值（最小堆）
void deleteMax(PriorityQueue *queue) {
if (isEmpty(queue)) {
      printf("Priority Queue is empty. Cannot delete element.\n");
      return;
}

// 将堆顶元素与队尾元素交换
queue->data[0] = queue->data[queue->size - 1];
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[leftChild] > queue->data[largest]) {
         largest = leftChild;
      }

      if (rightChild < queue->size && queue->data[rightChild] > queue->data[largest]) {
         largest = rightChild;
      }

      if (largest != i) {
         int temp = queue->data;
         queue->data = queue->data[largest];
         queue->data[largest] = 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，然后插入一些元素，查找并输出最大值，删除最大值，最后销毁队列。