PriorityQueue c++

优先队列（Priority Queue）是一种特殊的队列，其中的元素按照优先级进行排序。在C语言中，可以使用堆（heap）来实现优先队列。堆是一种二叉树结构，分为最大堆和最小堆两种类型。

在C中，可以使用数组来表示堆结构。需要定义一个数组来存储元素，并使用指针来指向堆顶元素。对于最大堆，堆顶元素是优先级最高的元素；而对于最小堆，堆顶元素是优先级最低的元素。

要实现一个优先队列，需要实现以下几个操作：
. 插入（Insert）：将一个元素插入到队列中，并保持优先级的顺序。
2. 删除（Remove）：删除队列中的一个元素，并返回该元素。
3. 查看（Peek）：查看队列中优先级最高的元素，但不删除它。

以下是一个使用C语言实现最大堆优先队列的示例代码：

#include <stdio.h>

#define MAX_SIZE 100

// 声明全局变量
int heap[MAX_SIZE];
int size = 0;

// 获取父节点的索引
int get_parent(int i) {
    return (i - 1) / 2;
}

// 获取左子节点的索引
int get_left_child(int i) {
    return 2 * i + 1;
}

// 获取右子节点的索引
int get_right_child(int i) {
    return 2 * i + 2;
}

// 上移操作，用于维护堆的性质
void shift_up(int i) {
    while (i > 0 && heap[i] > heap[get_parent(i)]) {
        // 交换当前节点和父节点的值
        int temp = heap[i];
        heap[i] = heap[get_parent(i)];
        heap[get_parent(i)] = temp;

        // 更新当前节点的索引
        i = get_parent(i);
    }
}

// 下移操作，用于维护堆的性质
void shift_down(int i) {
    int max_index = i;
    int left_child = get_left_child(i);
    int right_child = get_right_child(i);

    if (left_child < size && heap[left_child] > heap[max_index]) {
        max_index = left_child;
    }

    if (right_child < size && heap[right_child] > heap[max_index]) {
        max_index = right_child;
    }

    if (i != max_index) {
        // 交换当前节点和最大子节点的值
        int temp = heap[i];
        heap[i] = heap[max_index];
        heap[max_index] = temp;

        // 更新当前节点的索引
        shift_down(max_index);
    }
}

// 插入操作
void insert(int value) {
    if (size == MAX_SIZE) {
        printf("Heap is full.\n");
        return;
    }

    heap[size] = value;
    shift_up(size);
    size++;
}

// 删除操作
int remove_max() {
    if (size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int max_value = heap[0];
    heap[0] = heap[size - 1];
    size--;
    shift_down(0);

    return max_value;
}

// 查看操作
int peek() {
    if (size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    return heap[0];
}

// 打印堆中的元素
void print_heap() {
    printf("Heap: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main() {
    insert(10);
    insert(7);
    insert(15);
    insert(20);
    insert(5);

    print_heap(); // 输出：Heap: 20 10 15 7 5

    int max_value = remove_max();
    printf("Removed max value: %d\n", max_value); // 输出：Removed max value: 20

    print_heap(); // 输出：Heap: 15 10 5 7

    int top_value = peek();
    printf("Peeked value: %d\n", top_value); // 输出：Peeked value: 15

    return 0;
}

该示例代码实现了一个最大堆优先队列，通过数组来表示堆结构，并使用上移（shift_up）和下移（shift_down）操作来维护堆的性质。可以使用插入、删除和查看操作来操作优先队列中的元素，并使用打印堆函数来输出堆中的元素。