C++优先队列实现二叉堆

C语言中实现优先队列的经典方式是使用二叉堆数据结构。二叉堆是一种完全二叉树，同时满足堆次序的条件。在二叉堆中，每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。通过维护堆次序，可以保证堆顶元素是最大或最小的元素。

下面是C语言中实现二叉堆的优先队列的一种方法：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int capacity;  // 队列的容量
    int size;      // 队列中元素的数量
    int *data;     // 存储队列元素的数组
} PriorityQueue;

PriorityQueue* createPriorityQueue(int capacity) {
    PriorityQueue *queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    queue->capacity = capacity;
    queue->size = 0;
    queue->data = (int*)malloc(sizeof(int) * capacity);
    return queue;
}

void destroyPriorityQueue(PriorityQueue *queue) {
    free(queue->data);
    free(queue);
}

void enqueue(PriorityQueue *queue, int value) {
    if (queue->size >= queue->capacity) {
        // 队列已满，需要扩容
        queue->capacity *= 2;
        queue->data = (int*)realloc(queue->data, sizeof(int) * queue->capacity);
    }
    // 将元素放入队列尾部
    queue->data[queue->size] = value;
    queue->size++;
    // 通过向上调整操作恢复堆次序
    int child = queue->size - 1;
    int parent = (child - 1) / 2;
    while (child > 0 && queue->data[child] > queue->data[parent]) {
        int temp = queue->data[child];
        queue->data[child] = queue->data[parent];
        queue->data[parent] = temp;
        child = parent;
        parent = (child - 1) / 2;
    }
}

int dequeue(PriorityQueue *queue) {
    int value = queue->data[0];
    // 将队尾元素放到队首，并删除队尾元素
    queue->data[0] = queue->data[queue->size - 1];
    queue->size--;
    // 通过向下调整操作恢复堆次序
    int parent = 0;
    while (parent * 2 + 1 < queue->size) {
        int leftChild = parent * 2 + 1;
        int rightChild = parent * 2 + 2;
        int maxChild = leftChild;
        if (rightChild < queue->size && queue->data[rightChild] > queue->data[leftChild]) {
            maxChild = rightChild;
        }
        if (queue->data[parent] >= queue->data[maxChild]) {
            break;
        }
        int temp = queue->data[parent];
        queue->data[parent] = queue->data[maxChild];
        queue->data[maxChild] = temp;
        parent = maxChild;
    }
    return value;
}

int main() {
    PriorityQueue *queue = createPriorityQueue(10);
    enqueue(queue, 5);
    enqueue(queue, 3);
    enqueue(queue, 7);
    printf("%d\n", dequeue(queue));  // 输出7，因为7是队列中的最大值
    printf("%d\n", dequeue(queue));  // 输出5，因为5是队列中的次大值
    printf("%d\n", dequeue(queue));  // 输出3，因为3是队列中的最小值
    destroyPriorityQueue(queue);
    return 0;
}