详细解读 c++优先级队列 的原理 构造 用法

C 优先级队列是一种数据结构，它可以按照元素的优先级进行排序和访问。它的原理是通过使用堆来实现，堆是一种完全二叉树，它满足父节点的值总是大于或等于子节点的值（最大堆），或者父节点的值总是小于或等于子节点的值（最小堆）。

在 C 语言中，可以使用标准库中的 heap 实现优先级队列。构造一个优先级队列需要定义一个比较函数，用于比较元素的优先级。在使用优先级队列时，可以使用函数如 push、pop、top 等来实现元素的插入、删除和访问。

例如，以下是一个使用 C 优先级队列实现最小堆的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 100

typedef struct {
    int value;
    int priority;
} Node;

typedef struct {
    Node heap[MAX_SIZE];
    int size;
} PriorityQueue;

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

void push(PriorityQueue *q, Node node) {
    if (q->size >= MAX_SIZE) {
        printf("Priority queue is full.\n");
        return;
    }
    q->heap[q->size++] = node;
    int i = q->size - 1;
    while (i > 0 && q->heap[i].priority < q->heap[(i - 1) / 2].priority) {
        swap(&q->heap[i], &q->heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

Node pop(PriorityQueue *q) {
    if (q->size == 0) {
        printf("Priority queue is empty.\n");
        return (Node) {0, INT_MAX};
    }
    Node node = q->heap[0];
    q->heap[0] = q->heap[--q->size];
    int i = 0;
    while (i * 2 + 1 < q->size) {
        int j = i * 2 + 1;
        if (j + 1 < q->size && q->heap[j + 1].priority < q->heap[j].priority) {
            j++;
        }
        if (q->heap[i].priority <= q->heap[j].priority) {
            break;
        }
        swap(&q->heap[i], &q->heap[j]);
        i = j;
    }
    return node;
}

Node top(PriorityQueue *q) {
    if (q->size == 0) {
        printf("Priority queue is empty.\n");
        return (Node) {0, INT_MAX};
    }
    return q->heap[0];
}

int main() {
    PriorityQueue q = {0};
    push(&q, (Node) {1, 3});
    push(&q, (Node) {2, 2});
    push(&q, (Node) {3, 1});
    printf("%d\n", top(&q).value); // 3
    printf("%d\n", pop(&q).value); // 3
    printf("%d\n", top(&q).value); // 1
    return 0;
}

在这个示例中，我们定义了一个 Node 结构体，包含一个值和一个优先级。我们使用一个 PriorityQueue 结构体来表示优先级队列，其中 heap 数组用于存储元素，size 表示队列的大小。我们实现了 push、pop、top 等函数来实现元素的插入、删除和访问。在 push 函数中，我们使用了最小堆的原理来维护元素的优先级。在 pop 函数中，我们使用了堆的原理来删除队列中的元素，并返回优先级最高的元素。在 top 函数中，我们返回队列中优先级最高的元素，但不删除它。

总之，C 优先级队列是一种非常有用的数据结构，可以用于许多应用程序，例如任务调度、事件处理等。