c语言中的优先队列

在 C 语言中，优先队列可以使用堆来实现。堆是一种完全二叉树，分为最大堆和最小堆两种类型。最大堆要求父节点的值大于等于其子节点的值，最小堆要求父节点的值小于等于其子节点的值。

在实现优先队列时，可以使用最小堆来存储元素，保证队首元素是最小值。对于插入操作，先将元素插入到堆的末尾，然后执行上滤操作，将新元素上滤到合适的位置。对于弹出操作，将堆顶元素弹出，然后将堆末尾元素放到堆顶，执行下滤操作，将新堆顶元素下滤到合适的位置。

下面是一个简单的优先队列的实现示例，使用最小堆来存储元素：

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int size;
} Heap;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void up(Heap *heap, int index) {
    int parent = (index - 1) / 2;
    if (parent >= 0 && heap->data[parent] > heap->data[index]) {
        swap(&heap->data[parent], &heap->data[index]);
        up(heap, parent);
    }
}

void down(Heap *heap, int index) {
    int left = index * 2 + 1;
    int right = index * 2 + 2;
    int min = index;
    if (left < heap->size && heap->data[left] < heap->data[min]) {
        min = left;
    }
    if (right < heap->size && heap->data[right] < heap->data[min]) {
        min = right;
    }
    if (min != index) {
        swap(&heap->data[min], &heap->data[index]);
        down(heap, min);
    }
}

void insert(Heap *heap, int value) {
    heap->data[heap->size] = value;
    heap->size++;
    up(heap, heap->size - 1);
}

int pop(Heap *heap) {
    int value = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    down(heap, 0);
    return value;
}

int main() {
    Heap heap = {0};
    insert(&heap, 3);
    insert(&heap, 1);
    insert(&heap, 4);
    insert(&heap, 1);
    while (heap.size > 0) {
        printf("%d ", pop(&heap));
    }
    printf("\n");
    return 0;
}

输出结果为：1 1 3 4