感谢阅读我的博客，请认真看下去。我会尝试以最简单明了的语言讲清楚该算法的本质。

定义

优先队列（Priority Queue）是一种抽象数据类型，类似于普通的队列或栈，但它不是遵循先进先出（FIFO）或后进先出（LIFO）的原则，而是根据元素的优先级进行排序。每次从优先队列中移除元素时，总是移除具有最高优先级的元素。优先级的定义可以根据实际应用场景的不同而不同，例如数字大小、字母顺序或其他任何可以比较的标准。

特性

• 插入：可以向优先队列中添加一个元素。新元素会被放置在合适的位置，以保持队列的有序状态。
• 删除最高优先级元素：从优先队列中移除并返回具有最高优先级的元素。这通常是指队列中的最小或最大元素，取决于队列是按照升序还是降序排列的。
• 获取最高优先级元素：查看队列中优先级最高的元素，但不移除它。
• 改变优先级：某些优先队列支持修改已存在元素的优先级，然后自动重新调整队列以保持正确的顺序。

应用场景

优先队列的应用非常广泛，包括但不限于：

• 任务调度：操作系统中使用优先队列来管理进程调度，确保高优先级的任务优先得到处理。
• 图形算法：如Dijkstra算法中使用优先队列来找到两个顶点之间的最短路径。
• 数据压缩：霍夫曼编码算法
• 资源分配：在网络路由、内存管理和磁盘调度等领域中用于优化资源分配。
• 最短路径算法：Dijkstra算法；
• 最小生成树算法：Prim算法；
• 事件驱动仿真：顾客排队算法；
• 排序问题：查找第 k 个最小元素。

总之，优先队列是一个非常有用的数据结构，尤其适用于那些需要根据元素的某些特征进行排序和选择的场景。

实现方式

优先队列可以通过多种方式实现，最常见的有以下几种：

• 数组（顺序存储）实现优先队列：
  • 入队操作直接插入到数组队尾，时间复杂度为O(1)。出队操作需要遍历整个数组，找到优先级最高的元素，返回并删除该元素，时间复杂度为O(n)。
• 链表（链式存储）实现优先队列：
  • 链表中的元素按照优先级排序，入队操作需要为待插入元素创建节点，并在链表中找到合适的插入位置， 时间复杂度为O(n)。出队操作直接返回链表队头元素，并删除队头元素，时间复杂度为O(1)。
• 二叉堆结构实现优先队列：
  • 这是最常用的实现方式，因为它提供了很好的性能平衡。插入和删除操作的时间复杂度均为O(log n)。构建一个二叉堆结构，二叉堆按照优先级进行排序。入队操作就是将元素插入到二叉堆中合适位置，出队操作则返回二叉堆中优先级最大节点（根节点）并删除。之后重新调整二叉堆即可。
  • 知识点补充：堆是一种特殊的完全二叉树。所有父结点都比子结点要小的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。
• 斐波那契堆：
  • 一种更加复杂的堆结构，提供更好的渐近性能，但在实际应用中由于常数因子较大，可能不如二叉堆表现好。
• 平衡二叉搜索树：
  • 如红黑树或AVL树也可以用来实现优先队列，这些数据结构支持高效的插入、删除和查找操作。
• 跳表：
  • 一种概率性的数据结构，能够提供平均O(log n)的插入和删除时间。

代码实现（使用堆实现 C语言）

第一步，定义优先队列的数据结构

定义优先队列的数据结构，包括数组、当前元素数量和数组的最大容量。并实现初始化及销毁方法。

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

typedef struct {
    int *array;     // 存储元素的数组
    int capacity;   // 数组的最大容量
    int curSize;       // 当前元素数量
} PriorityQueue;

// 初始化优先队列
PriorityQueue* initPriorityQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    pq->array = (int*)malloc(capacity * sizeof(int));
    pq->capacity = capacity;
    pq->curSize = 0;
    return pq;
}

// 销毁优先队列
void destroyPriorityQueue(PriorityQueue *pq) {
    free(pq->array);
    free(pq);
}

第二步，实现优先队列的插入操作

插入一个新的元素到优先队列中末尾，然后调整并保持堆的性质。

void insert(PriorityQueue *pq, int value) {
    // 判断优先队列是否已经满了，满了则直接return
    if (pq->curSize == pq->capacity) {
        printf("Priority queue is full\n");
        return;
    }

    // 将元素插入优先队列末尾，需要注意此时会破坏最小堆的性质。
    int index = pq->curSize;
    pq->array[index] = value;
    pq->curSize++;

    // 调整堆，保持最小堆性质
    while (index > 0 && (pq->array[(index - 1) / 2] > pq->array[index])) {
        int temp = pq->array[(index - 1) / 2];
        pq->array[(index - 1) / 2] = pq->array[index];
        pq->array[index] = temp;
        index = (index - 1) / 2;
    }
}

代码解释（写给小白看）：

• while循环的代码逻辑：

  • 条件index > 0：确保当前节点不是根节点（根节点没有父节点）。
  • 条件(pq->array[(index - 1) / 2] > pq->array[index])： 其中pq->array[(index - 1) / 2]是pq->array[index]的父节点。在此while循环中的目的是确保当前节点的值小于其父节点的值。如果当前节点的值小于其父节点的值，则需要交换它们的位置，以保持最小堆的性质。
  • 交换节点并更新索引：
    • int temp = pq->array[(index - 1) / 2];：保存父节点的值到temp。
    • pq->array[(index - 1) / 2] = pq->array[index];：将当前节点的值赋给父节点。
    • pq->array[index] = temp;：将原来父节点的值赋给当前节点。
    • index = (index - 1) / 2;：将当前节点的索引更新为其父节点的索引。然后进入下一轮循环向上检查并继续调整堆直到调整完毕。

• 常见问题：为什么pq->array[(index - 1) / 2]是pq->array[index]的父节点？

  • 答曰：二叉堆通常用一个数组来表示，其中每个节点的索引与其子节点和父节点的索引之间有明确的关系。
  • 假设数组的索引是从0开始的，那么对于一个索引为 index 的节点有如下性质：
    • 其左子节点的索引为 2 * index + 1
    • 其右子节点的索引为 2 * index + 2
    • 其父亲节点的索引为 (index - 1) / 2

第三步，实现优先队列的删除操作

删除优先队列中的最小元素，然后调整并保持堆的性质。最后返回最小值。

int deleteMin(PriorityQueue *pq) {
    // 判断当前优先队列是否为空，空则无法删除，直接return
    if (pq->curSize == 0) {
        printf("Priority queue is empty\n");
        return -1;
    }

    // 删除最小元素，注意此时会破坏最小二叉堆的性质。
    int min = pq->array[0];
    // 将最后一个元素放到堆的顶端，从而保证pq仍然是一个完全二叉树，不至于直接被一劈两半。
    pq->array[0] = pq->array[pq->curSize - 1]; 
    pq->curSize--;

    // 调整并保持堆的性质
    int index = 0;
    while (index < pq->curSize) {
        int leftChild = 2 * index + 1;   // 左儿子
        int rightChild = 2 * index + 2;  // 右儿子
        int smallest = index;
        
         // 找到最小元素的索引
        if ((leftChild < pq->curSize) && (pq->array[leftChild] < pq->array[smallest])) {
            smallest = leftChild;
        }
        if (rightChild < pq->curSize && pq->array[rightChild] < pq->array[smallest]) {
            smallest = rightChild;
        }
        
        // 将找到的最小元素与当前元素交换。
        if (smallest != index) {
            int temp = pq->array[smallest];
            pq->array[smallest] = pq->array[index];
            pq->array[index] = temp;
            index = smallest;
        } else {
            break; // 说明当前节点已经是其子节点中的最小值节点，不需要再进行调整
        }
    }

    return min;
}

最后使用main函数调用

int main() {
    // 初始化一个最大容量为10的优先队列。
    PriorityQueue *pq = initPriorityQueue(10);

    insert(pq, 5);
    insert(pq, 3);
    insert(pq, 8);
    insert(pq, 1);
    insert(pq, 2);
    printf("当前优先队列为：");
    for (int i = 0;i< pq->curSize;i++) {
        printf("%d ",pq->array[i]);
    }
    printf("\n最小元素为: %d\n", deleteMin(pq)); // 输出 1
    
    printf("当前优先队列为：");
    for (int i = 0;i< pq->curSize;i++) {
        printf("%d ",pq->array[i]);
    }
    printf("\n最小元素为: %d\n", deleteMin(pq)); // 输出 2
    
    printf("当前优先队列为：");
    for (int i = 0;i< pq->curSize;i++) {
        printf("%d ",pq->array[i]);
    }
    printf("\n");
    destroyPriorityQueue(pq);
    return 0;
}