C++ 优先队列（Priority Queue）核心原理与实战应用

C++ 优先队列（Priority Queue）详解

在 C++ 编程中，数据结构是处理数据的核心工具。在众多结构中，**优先队列（Priority Queue）**因其独特的排序机制而占据重要地位。与普通队列不同，它不遵循先进先出（FIFO）原则，而是根据元素的优先级进行调度。

一、优先队列的概念

想象一个特殊的队伍，成员不是按到达顺序排队，而是根据'重要性'标签排列。例如医院急诊室，重伤患者会优先得到救治。优先队列正是如此：优先级最高的元素始终位于队首，随时准备被处理。

二、C++ 中的使用方式

1. 默认行为：最大堆

C++ STL 提供的 priority_queue 类默认实现的是大顶堆。包含 <queue> 头文件后，最大的元素会自动排在队首。

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(10);
    pq.push(3);
    
    std::cout << "队首元素（最大值）: " << pq.top() << std::endl;
    pq.pop();
    std::cout << "队首元素（最大值）: " << pq.top() << std::endl;
    return 0;
}

每次 push 都会自动调整堆结构，top 获取当前最大值，pop 移除队首元素。

2. 自定义规则：最小堆

若需小顶堆（最小值在队首），可定义比较函数或函数对象。

#include <iostream>
#include <queue>
#include <vector>

struct Compare {
    bool operator()(int a, int b) {
        return a > b; // 返回 true 表示 a 的优先级低于 b
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, Compare> pq;
    pq.push(5);
    pq.push(10);
    pq.push(3);
    
    std::cout << "队首元素（最小值）: " << pq.top() << std::endl;
    return 0;
}

通过重载 operator()，我们可以灵活控制元素的排序逻辑。

三、底层原理：二叉堆

priority_queue 的底层通常由**二叉堆（Binary Heap）**实现。这是一种完全二叉树结构，分为大顶堆和小顶堆。

• 大顶堆：父节点值大于等于子节点值。
• 小顶堆：父节点值小于等于子节点值。

1. 插入操作（Push）

新元素加入时，先放在末尾，然后向上调整（Sift Up），直到满足堆性质。

template<typename T>
void siftUp(std::vector<T>& heap, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap[parent] < heap[idx]) { // 大顶堆示例
            std::swap(heap[parent], heap[idx]);
            idx = parent;
        } else {
            break;
        }
    }
}

2. 删除操作（Pop）

删除队首元素时，将最后一个元素移至队首，然后向下调整（Sift Down）。

template<typename T>
void siftDown(std::vector<T>& heap, int idx, int size) {
    int largest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < size && heap[left] > heap[largest])
        largest = left;
    if (right < size && heap[right] > heap[largest])
        largest = right;

    if (largest != idx) {
        std::swap(heap[idx], heap[largest]);
        siftDown(heap, largest, size);
    }
}

四、典型应用场景

1. 任务调度

操作系统或任务管理系统常利用优先队列管理任务。高优先级任务（如紧急工单）会被优先处理。

#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Task {
    std::string name;
    int priority;
    Task(const std::string& n, int p) : name(n), priority(p) {}
};

struct TaskCompare {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority; // 优先级高的在前
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, TaskCompare> taskQueue;
    taskQueue.push(Task("任务 1", 5));
    taskQueue.push(Task("任务 2", 3));
    taskQueue.push(Task("任务 3", 8));

    while (!taskQueue.empty()) {
        Task currentTask = taskQueue.top();
        std::cout << "正在处理任务：" << currentTask.name 
                  << "，优先级：" << currentTask.priority << std::endl;
        taskQueue.pop();
    }
    return 0;
}

2. 图算法：Dijkstra 最短路径

在寻找单源最短路径时，优先队列能高效选出当前距离起点最近的未访问节点。

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

struct Node {
    int id;
    int distance;
    std::vector<Node*> neighbors;
    Node(int i) : id(i), distance(INT_MAX) {}
};

struct NodeCompare {
    bool operator()(const Node* n1, const Node* n2) {
        return n1->distance > n2->distance; // 距离小的优先
    }
};

void dijkstra(Node* source) {
    std::priority_queue<Node*, std::vector<Node*>, NodeCompare> pq;
    source->distance = 0;
    pq.push(source);

    while (!pq.empty()) {
        Node* currentNode = pq.top();
        pq.pop();

        for (Node* neighbor : currentNode->neighbors) {
            int newDist = currentNode->distance + 1;
            if (newDist < neighbor->distance) {
                neighbor->distance = newDist;
                pq.push(neighbor);
            }
        }
    }
}

3. 数据压缩：哈夫曼编码

构建哈夫曼树时，优先队列用于反复选取频率最低的两个节点合并，从而生成最优前缀码。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

struct HuffmanNode {
    char data;
    int frequency;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), right(nullptr) {}
};

struct HuffmanNodeCompare {
    bool operator()(const HuffmanNode* n1, const HuffmanNode* n2) {
        return n1->frequency > n2->frequency; // 频率低的优先
    }
};

HuffmanNode* buildHuffmanTree(const std::unordered_map<char, int>& freqMap) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, HuffmanNodeCompare> pq;

    for (const auto& pair : freqMap) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }

    while (pq.size() > 1) {
        HuffmanNode* leftNode = pq.top(); pq.pop();
        HuffmanNode* rightNode = pq.top(); pq.pop();
        HuffmanNode* parentNode = new HuffmanNode('\0', leftNode->frequency + rightNode->frequency);
        parentNode->left = leftNode;
        parentNode->right = rightNode;
        pq.push(parentNode);
    }
    return pq.top();
}

通过上述示例可以看出，优先队列在需要动态维护有序性的场景中具有不可替代的作用。掌握其原理与用法，能让代码在处理复杂逻辑时更加高效。