基于最小堆实现的自定义优先级队列出现异常行为

我用C++基于最小堆实现了一个优先级队列，采用向量零索引（索引i的左右子节点为2i+1和2i+2），使用递归的swim和sink函数。实现代码如下：

#include <iostream>
#include <vector>

using namespace std;

template <class t>
class priorityqueue
{
private:
    vector<t> vec;

    inline static void swap(t *x, t *y)
    {
        t temp = *x;
        *x = *y;
        *y = temp;
    }

    inline static size_t left(size_t i) { return (i << 1) + 1; }

    inline static size_t right(size_t i) { return (i << 1) + 2; }

    inline static size_t up(size_t i) { return (i - 1) >> 1; }

    inline bool validindex(size_t i) { return i < vec.size(); }

    inline void swim(size_t i)
    {
        if (i == 0)
            return;
        size_t up_ = up(i);
        if (vec[i] < vec[up_])
        {
            swap(&vec[i], &vec[up_]);
            swim(up_);
        }
    }

    inline void sink(size_t i)
    {
        size_t left_ = left(i), right_ = right(i);
        if (!validindex(left_))
        {
            return;
        }
        if (!validindex(right_))
        {
            if (vec[i] > vec[left_])
            {
                swap(&vec[i], &vec[left_]);
                sink(left_);
            }
            return;
        }
        if (vec[i] < vec[left_])
        {
            if (vec[i] < vec[right_])
            {
                return;
            }
            swap(&vec[i], &vec[right_]);
            sink(right_);
        }
        else
        {
            if (vec[i] < vec[right_])
            {
                swap(&vec[i], &vec[left_]);
                sink(left_);
            }
            else
            {
                if (vec[left_] < vec[right_])
                {
                    swap(&vec[i], &vec[left_]);
                    sink(left_);
                }
                else
                {
                    swap(&vec[i], &vec[right_]);
                    sink(right_);
                }
            }
        }
    }

public:
    size_t size() { return vec.size(); }

    bool empty() { return size() == 0; }

    void push(t elem)
    {
        vec.push_back(elem);
        swim(vec.size() - 1);
    }

    t peek()
    {
        return vec[0];
    }

    t pop()
    {
        t elem = vec[0];
        t last = vec[vec.size() - 1];
        swap(&last, &elem);
        vec.pop_back();
        sink(0);
        return elem;
    }
};

int main()
{
    priorityqueue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    pq.push(2);
    pq.push(6);
    pq.push(5);
    pq.push(3);
    while (!pq.empty())
    {
        cout << pq.pop() << " ";
    }
}

实际运行输出：

(base) miglanigursimar@Miglanis-MacBook-Pro priorityqueue % ./a.out 
5 5 6 4 9 3 3 2 1 1 %

预期输出应为升序的π前10位数字：1 1 2 3 3 4 5 5 6 9

核心问题：pop函数的交换逻辑错误 #

在pop方法中，你交换的是局部变量elem和last，而非向量中的实际元素，导致堆的结构完全没有被正确修改。局部变量的交换不会影响vec容器内的元素，相当于每次只是取出堆顶元素，然后直接删除最后一个元素，完全破坏了堆的结构。

修复后的pop函数：

t pop()
{
    if (empty()) {
        throw std::runtime_error("Cannot pop from empty priority queue");
    }
    t elem = vec[0];
    // 直接交换堆顶与容器最后一个元素
    swap(&vec[0], &vec[vec.size() - 1]);
    vec.pop_back();
    sink(0);
    return elem;
}

可选优化：简化sink函数逻辑 #

原sink函数的嵌套条件判断过于复杂，容易出错。可以简化为先找到当前节点的最小子节点，若当前节点大于该子节点则交换并递归下沉，逻辑更清晰：

inline void sink(size_t i)
{
    size_t smallest = i;
    size_t left_ = left(i);
    size_t right_ = right(i);

    // 找到当前节点及其子节点中的最小值索引
    if (validindex(left_) && vec[left_] < vec[smallest]) {
        smallest = left_;
    }
    if (validindex(right_) && vec[right_] < vec[smallest]) {
        smallest = right_;
    }

    // 如果当前节点不是最小值，交换后继续下沉
    if (smallest != i) {
        swap(&vec[i], &vec[smallest]);
        sink(smallest);
    }
}

修复后运行程序，将得到预期的升序输出：1 1 2 3 3 4 5 5 6 9

内容的提问来源于stack exchange，提问作者Xowaga