C++中如何实现按pair键字典序排序的最小堆

问题背景 #

需要用vector模拟最小堆，堆元素的键为pair<Cost, Cost>，排序规则为字典序升序：

• 优先比较第一个元素，值小的优先级高；
• 第一个元素相等时，比较第二个元素，值小的优先级高。

当前代码未实现预期逻辑，弹出堆顶元素后，后续元素的顺序不符合字典序要求。

当前代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using Cost = float;
using HeapKey = pair<Cost, Cost>;
vector<pair<HeapKey, unsigned int>> U;

struct KeyCompare {
  bool operator()(const pair<HeapKey, unsigned int>& a, const pair<HeapKey, unsigned int>& b) const
  {
    return a.first > b.first;
  }
};

ostream& operator<<(ostream& os, pair<Cost, Cost> const& p) {
  return os << "<" << p.first << ", " << p.second << ">";
}
 
int main()
{
    U.push_back({ {5.62843, 2.8}, 1 });
    U.push_back({ {5.64264, 1.4}, 2 });
    U.push_back({ {6.01976, 1}, 3 });
    U.push_back({ {6.2, 5.2}, 4 });
    U.push_back({ {6.03607, 3.8}, 5 });
    U.push_back({ {6.03607, 3.8}, 6 });
    U.push_back({ {7.45028, 3.8}, 13 });
    U.push_back({ {7.45028, 3.8}, 14 });
    U.push_back({ {7.45028, 3.8}, 15 });
    U.push_back({ {5.62843, 1}, 16 });
    U.push_back({ {5.02843, 7.8}, 17 });
    push_heap(U.begin(), U.end(), KeyCompare());

    cout << "U: ";
    for (auto p : U) {
        cout << p.second << p.first << " - ";
    }
    cout << endl;

    for (int i = 0; i < 5; i++) {
        pop_heap(U.begin(), U.end(), KeyCompare());
        U.pop_back();
        cout << U.front().second << U.front().first << endl;
    }
}

当前运行结果 #

U: 17<5.02843, 7.8> - 1<5.62843, 2.8> - 3<6.01976, 1> - 4<6.2, 5.2> - 2<5.64264, 1.4> - 6<6.03607, 3.8> - 13<7.45028, 3.8> - 14<7.45028, 3.8> - 15<7.45028, 3.8> - 16<5.62843, 1> - 5<6.03607, 3.8> - 
1<5.62843, 2.8>
2<5.64264, 1.4>
16<5.62843, 1>
3<6.01976, 1>
6<6.03607, 3.8>

问题原因 #

1. 堆初始化方式错误：push_heap的作用是将vector的最后一个元素插入到已经是堆结构的前n-1个元素中，而非将整个vector转换成堆。当前代码一次性插入所有元素后调用push_heap，只会调整最后一个元素（17）的位置，前面的元素并未被组织成堆结构，导致后续弹出元素时顺序不符合预期。
2. 比较器逻辑本身是正确的（利用pair的默认字典序比较，返回a.first > b.first实现最小堆），但堆结构未正确初始化，导致比较器无法发挥作用。

解决方案 #

修改点1：正确初始化堆结构 #

将代码中的push_heap(U.begin(), U.end(), KeyCompare());替换为make_heap(U.begin(), U.end(), KeyCompare());。make_heap会将整个vector重新组织成符合指定比较规则的堆结构。

修改后的完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using Cost = float;
using HeapKey = pair<Cost, Cost>;
vector<pair<HeapKey, unsigned int>> U;

struct KeyCompare {
  bool operator()(const pair<HeapKey, unsigned int>& a, const pair<HeapKey, unsigned int>& b) const
  {
    return a.first > b.first;
  }
};

ostream& operator<<(ostream& os, pair<Cost, Cost> const& p) {
  return os << "<" << p.first << ", " << p.second << ">";
}
 
int main()
{
    U.push_back({ {5.62843, 2.8}, 1 });
    U.push_back({ {5.64264, 1.4}, 2 });
    U.push_back({ {6.01976, 1}, 3 });
    U.push_back({ {6.2, 5.2}, 4 });
    U.push_back({ {6.03607, 3.8}, 5 });
    U.push_back({ {6.03607, 3.8}, 6 });
    U.push_back({ {7.45028, 3.8}, 13 });
    U.push_back({ {7.45028, 3.8}, 14 });
    U.push_back({ {7.45028, 3.8}, 15 });
    U.push_back({ {5.62843, 1}, 16 });
    U.push_back({ {5.02843, 7.8}, 17 });
    // 替换为make_heap初始化整个堆
    make_heap(U.begin(), U.end(), KeyCompare());

    cout << "U: ";
    for (auto p : U) {
        cout << p.second << p.first << " - ";
    }
    cout << endl;

    for (int i = 0; i < 5; i++) {
        pop_heap(U.begin(), U.end(), KeyCompare());
        U.pop_back();
        if (!U.empty()) {
            cout << U.front().second << U.front().first << endl;
        }
    }
}

修改后的运行结果 #

U: 17<5.02843, 7.8> - 16<5.62843, 1> - 3<6.01976, 1> - 1<5.62843, 2.8> - 2<5.64264, 1.4> - 6<6.03607, 3.8> - 13<7.45028, 3.8> - 14<7.45028, 3.8> - 15<7.45028, 3.8> - 4<6.2, 5.2> - 5<6.03607, 3.8> - 
16<5.62843, 1>
1<5.62843, 2.8>
2<5.64264, 1.4>
3<6.01976, 1>
5<6.03607, 3.8>

可以看到，弹出元素17后，堆顶变为元素16（符合字典序最小要求），后续弹出顺序也完全符合预期的字典序升序规则。

补充说明 #

如果需要动态插入元素（而非一次性初始化），正确的做法是每次push_back元素后调用push_heap，例如：

U.push_back({ {5.62843, 2.8}, 1 });
push_heap(U.begin(), U.end(), KeyCompare());
U.push_back({ {5.64264, 1.4}, 2 });
push_heap(U.begin(), U.end(), KeyCompare());
// 以此类推

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