C++ STL 容器适配器：优先队列 priority_queue 原理与实现

为空返回 true；不为空返回 false

删除堆顶元素

V.pop();

优先队列的模拟实现

类模板

template <class T, class Container = std::vector<T>>
class priority_queue {
public:
    // 构造可以不写，因为可以直接使用 vector
    // 函数实现
private:
    Container x;
};

既然底层是 vector，我们用缺省参数直接实例化出一个 vector 类型的变量就可以作为底层实现了。

插入元素

插入元素调用 vector 的接口就行了，这里由于需要满足优先队列的性质（大顶堆），我们还需要在插入之后使用向上调整，保证堆顶（首元素）是最大的。

插入元素：

// 插入数据
void push(const T& data) {
    x.push_back(data);
    // 向上调整
    PushUp(size() - 1);
}

向上调整：

// 向上调整
void PushUp(int child) {
    // 父节点
    int parent = (child - 1) / 2;
    // 如果孩子节点大于父节点，就向上调整交换（根节点可能也需要调整）
    while (parent >= 0) {
        // 只要进入循环，那么节点下标一定是在合法范围
        if (x[child] > x[parent]) {
            // 交换
            std::swap(x[child], x[parent]);
            // 更新孩子、父节点
            child = parent;
            parent = (child - 1) / 2;
        } else break;
    }
}

访问元素

访问第一个元素即可（堆顶元素）

// 访问元素
T top() {
    return x[0];
}

获取元素个数

// 计算元素个数
size_t size() {
    return x.size();
}

判断优先队列是否为空

// 判断是否为空
bool empty() {
    return x.empty();
}

删除堆顶元素

这里的删除调用 vector 的尾删即可。 删除的方法：先交换堆顶 和 尾部元素，再删除，再使用向下调整保证大顶堆的性质。

// 删除堆顶元素
void pop() {
    PopDown(size() - 1);
}

向下调整：

// 向下调整
void PopDown(int child) {
    // 交换堆顶和末尾元素
    std::swap(x[child], x[0]);
    // 去尾
    x.pop_back();
    // 父子节点
    int parent = 0;
    child = 2 * parent + 1;
    // 开始调整（子节点不能超过范围）
    while (child < x.size()) {
        // 如果右节点大于左节点
        if (child + 1 < x.size() && x[child] < x[child + 1]) {
            child++;
        }
        // 如果父节点小于子节点
        if (x[parent] < x[child]) {
            std::swap(x[parent], x[child]);
            // 更新
            parent = child;
            child = 2 * parent + 1;
        } else break;
    }
}

效果展示

void test1_t() {
    priority_queue<int> V1;
    // 插入元素
    V1.push(10);
    V1.push(15);
    V1.push(5);
    V1.push(20);
    V1.push(0);
    V1.push(25);
    // 元素个数
    std::cout << V1.size() << std::endl;
    // 访问堆顶元素
    std::cout << V1.top() << std::endl;
    // 出堆顶元素
    V1.pop();
    // 访问堆顶元素
    std::cout << V1.top() << std::endl;
    // 判断是否为空
    std::cout << V1.empty() << std::endl;
}