C語言中,優先隊列可以通過使用堆(heap)來實現。堆是一種特殊的二叉樹結構,滿足以下兩個性質:
下面是使用C語言實現優先隊列的示例代碼:
#include <stdio.h>
#include <stdlib.h>
// 定義優先隊列結構
typedef struct {
int *arr; // 存儲元素的數組
int size; // 隊列的當前大小
int capacity; // 隊列的最大容量
} PriorityQueue;
// 初始化優先隊列
PriorityQueue* initPriorityQueue(int capacity) {
PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
queue->arr = (int*)malloc(sizeof(int) * (capacity + 1));
queue->size = 0;
queue->capacity = capacity;
return queue;
}
// 交換元素
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 上浮操作
void swim(PriorityQueue* queue, int k) {
while (k > 1 && queue->arr[k / 2] < queue->arr[k]) {
swap(&(queue->arr[k / 2]), &(queue->arr[k]));
k = k / 2;
}
}
// 下沉操作
void sink(PriorityQueue* queue, int k) {
while (2 * k <= queue->size) {
int j = 2 * k;
if (j < queue->size && queue->arr[j] < queue->arr[j + 1]) {
j++;
}
if (queue->arr[k] >= queue->arr[j]) {
break;
}
swap(&(queue->arr[k]), &(queue->arr[j]));
k = j;
}
}
// 插入元素
void insert(PriorityQueue* queue, int val) {
if (queue->size == queue->capacity) {
printf("Priority queue is full.\n");
return;
}
queue->arr[++queue->size] = val;
swim(queue, queue->size);
}
// 刪除最大元素
int deleteMax(PriorityQueue* queue) {
if (queue->size == 0) {
printf("Priority queue is empty.\n");
return -1;
}
int max = queue->arr[1];
swap(&(queue->arr[1]), &(queue->arr[queue->size--]));
sink(queue, 1);
return max;
}
// 打印優先隊列
void printPriorityQueue(PriorityQueue* queue) {
printf("Priority Queue: ");
for (int i = 1; i <= queue->size; i++) {
printf("%d ", queue->arr[i]);
}
printf("\n");
}
int main() {
PriorityQueue* queue = initPriorityQueue(10);
insert(queue, 3);
insert(queue, 10);
insert(queue, 5);
insert(queue, 1);
printPriorityQueue(queue);
int max = deleteMax(queue);
printf("Delete max: %d\n", max);
printPriorityQueue(queue);
free(queue->arr);
free(queue);
return 0;
}
在上述代碼中,我們使用了一個數組來存儲優先隊列的元素,數組的第一個元素不使用,從數組的第二個元素開始存儲元素。通過 swim
和 sink
操作來維持優先隊列的性質,其中 swim
操作用于插入元素后的上浮操作,sink
操作用于刪除元素后的下沉操作。 insert
函數用于插入元素, deleteMax
函數用于刪除最大元素。在 main
函數中,我們演示了優先隊列的使用過程。