C语言如何实现优先队列？

C语言中的优先队列（Priority Queue）

在C语言中,没有内置的优先队列数据结构，但我们可以使用不同的方法来实现它，以下是几种常见的实现方式：

使用标准库函数（qsort）

#include <stdio.h>
#include <stdlib.h>
// 定义优先队列元素结构
typedef struct {
    int value;
    int priority;
} PriorityQueueItem;
// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    PriorityQueueItem *itemA = (PriorityQueueItem *)a;
    PriorityQueueItem *itemB = (PriorityQueueItem *)b;
    return itemB->priority - itemA->priority; // 降序排列
}
void priority_queue_enqueue(PriorityQueueItem **queue, int *size, int capacity, int value, int priority) {
    if (*size >= capacity) {
        printf("Queue is full!\n");
        return;
    }
    queue[*size].value = value;
    queue[*size].priority = priority;
    (*size)++;
    // 每次插入后重新排序
    qsort(*queue, *size, sizeof(PriorityQueueItem), compare);
}
int priority_queue_dequeue(PriorityQueueItem **queue, int *size) {
    if (*size == 0) {
        printf("Queue is empty!\n");
        return -1;
    }
    int value = (*queue)[0].value;
    (*size)--;
    // 将最后一个元素移到开头
    for (int i = 0; i < *size; i++) {
        (*queue)[i] = (*queue)[i+1];
    }
    return value;
}
void print_queue(PriorityQueueItem *queue, int size) {
    for (int i = 0; i < size; i++) {
        printf("(%d, %d) ", queue[i].value, queue[i].priority);
    }
    printf("\n");
}
int main() {
    int capacity = 5;
    int size = 0;
    PriorityQueueItem *queue = malloc(capacity * sizeof(PriorityQueueItem));
    priority_queue_enqueue(&queue, &size, capacity, 10, 2);
    priority_queue_enqueue(&queue, &size, capacity, 20, 5);
    priority_queue_enqueue(&queue, &size, capacity, 30, 1);
    priority_queue_enqueue(&queue, &size, capacity, 40, 3);
    printf("Queue after enqueues: ");
    print_queue(queue, size);
    printf("Dequeued: %d\n", priority_queue_dequeue(&queue, &size));
    printf("Queue after dequeue: ");
    print_queue(queue, size);
    free(queue);
    return 0;
}

使用堆（Heap）实现更高效的优先队列

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
    int *array;
    int size;
    int capacity;
} PriorityQueue;
PriorityQueue* create_priority_queue(int capacity) {
    PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->array = (int*)malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
void heapify_up(PriorityQueue *pq, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (pq->array[index] > pq->array[parent]) {
            swap(&pq->array[index], &pq->array[parent]);
            index = parent;
        } else {
            break;
        }
    }
}
void heapify_down(PriorityQueue *pq, int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < pq->size && pq->array[left] > pq->array[largest]) {
        largest = left;
    }
    if (right < pq->size && pq->array[right] > pq->array[largest]) {
        largest = right;
    }
    if (largest != index) {
        swap(&pq->array[index], &pq->array[largest]);
        heapify_down(pq, largest);
    }
}
void enqueue(PriorityQueue *pq, int value) {
    if (pq->size == pq->capacity) {
        printf("Queue is full!\n");
        return;
    }
    pq->array[pq->size] = value;
    heapify_up(pq, pq->size);
    pq->size++;
}
int dequeue(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Queue is empty!\n");
        return -1;
    }
    int max = pq->array[0];
    pq->array[0] = pq->array[pq->size - 1];
    pq->size--;
    heapify_down(pq, 0);
    return max;
}
void print_queue(PriorityQueue *pq) {
    for (int i = 0; i < pq->size; i++) {
        printf("%d ", pq->array[i]);
    }
    printf("\n");
}
int main() {
    PriorityQueue *pq = create_priority_queue(MAX_SIZE);
    enqueue(pq, 10);
    enqueue(pq, 20);
    enqueue(pq, 5);
    enqueue(pq, 30);
    printf("Queue after enqueues: ");
    print_queue(pq);
    printf("Dequeued: %d\n", dequeue(pq));
    printf("Queue after dequeue: ");
    print_queue(pq);
    free(pq->array);
    free(pq);
    return 0;
}

使用第三方库

如果你可以使用第三方库,可以考虑：

1. GLib：提供GPriorityQueue
2. GNU C Library (glibc)：提供了类似的优先队列实现
3. CPQ：一个专门的C语言优先队列库

1. 时间复杂度：

   • 使用qsort实现：插入O(n)，删除O(n)
   • 使用堆实现：插入O(log n)，删除O(log n)

2. 选择哪种实现：

   • 对于小规模数据,qsort实现更简单
   • 对于大规模数据,堆实现更高效

3. 扩展性：

   
   （图片来源网络，侵删）
   • 可以根据需要修改为支持任意数据类型
   • 可以添加优先级的自定义比较函数

示例都是最大堆实现（最高优先级先出），如需最小堆，只需修改比较逻辑即可。