优先队列

优先队列是一种特殊的队列，其中每个元素都有一个优先级。在插入元素时，会根据其优先级将其插入队列中的适当位置。而在弹出元素时，会先弹出优先级最高的元素。

优先队列可以用于许多问题的求解，例如 Dijkstra最短路径算法和 Huffman编码算法等。

以下是一个基于数组的简单优先队列的 C 语言实现：

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

#define MAX_HEAP_SIZE 100

typedef struct {
    int priority;
    int data;
} Element;

typedef struct {
    Element heap[MAX_HEAP_SIZE];
    int size;
} PriorityQueue;

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

void heapify_up(PriorityQueue* queue, int i) {
    if (i == 0) {
        return;
    }

    int parent = (i - 1) / 2;

    if (queue->heap[parent].priority < queue->heap[i].priority) {
        swap(&queue->heap[parent], &queue->heap[i]);
        heapify_up(queue, parent);
    }
}

void heapify_down(PriorityQueue* queue, int i) {
    int left_child = 2 * i + 1;
    int right_child = 2 * i + 2;
    int max = i;

    if (left_child < queue->size && queue->heap[left_child].priority > queue->heap[max].priority) {
        max = left_child;
    }

    if (right_child < queue->size && queue->heap[right_child].priority > queue->heap[max].priority) {
        max = right_child;
    }

    if (max != i) {
        swap(&queue->heap[max], &queue->heap[i]);
        heapify_down(queue, max);
    }
}

void push(PriorityQueue* queue, int priority, int data) {
    if (queue->size == MAX_HEAP_SIZE) {
        printf("Queue is full\n");
        return;
    }

    Element element = {priority, data};
    queue->heap[queue->size] = element;
    queue->size++;

    heapify_up(queue, queue->size - 1);
}

Element pop(PriorityQueue* queue) {
    if (queue->size == 0) {
        printf("Queue is empty\n");
        return (Element) {0, 0};
    }

    Element element = queue->heap[0];
    queue->size--;
    queue->heap[0] = queue->heap[queue->size];

    heapify_down(queue, 0);

    return element;
}

int main() {
    PriorityQueue queue = { {0}, 0};

    push(&queue, 2, 20);
    push(&queue, 5, 50);
    push(&queue, 1, 10);
    push(&queue, 4, 40);

    while (queue.size > 0) {
        Element element = pop(&queue);
        printf("Priority: %d, Data: %d\n", element.priority, element.data);
    }

    return 0;
}