0

在 C++ 中，当添加到调用 bubbleUp 函数的 minHeap 时，如何按字典顺序比较两个具有相同优先级的事物？

我希望按字典顺序比较时较小的值在堆中排在第一位。if 条件应该是什么？

如果代码是这样的：

void MinHeap::bubbleUp(int pos)
{
    if (pos >= 0 && vec[pos].second < vec[(pos-1)/d].second)]  
    {
        swap(vec[pos], vec[(pos-1)/d)];
        bubbleUp(vec[(pos-1)/d)];
    }
    else if (pos >= 0 && vec[pos].second == vec[(pos-1)/d].second)
    {
        if(vec[pos].first < vec[(pos-1)/d].first)
        {
            swap(vec[pos], vec[(pos-1)/d];
            bubbleup((pos-1)/d];
        }
    }
}

作为参考，向量包含一对字符串和优先级。

4

1 回答 1

0

如果您想要数据的特定排序顺序，您可以使用内置比较函数来表示“某事大于其他”，或者您可以提供自定义排序 Functor。

为了使用 Functor，您需要使用std::priority_queue所有 3 个模板参数来实例化（MinHeap）。最后一个将是比较函子。

作为底层容器，您可以使用std::vector.

示例程序可能如下所示：

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

struct MyData {
    int a{};
    int b{};
    friend std::ostream& operator << (std::ostream& os, const MyData& m) {
        return os << "a: " << m.a << "   b: " << m.b << '\n';
    }
};

struct Compare {
    bool operator()(const MyData& md1, const MyData& md2) {
        if (md1.a == md2.a)
            return md1.b > md2.b;
        else
            return md1.a > md2.a;
    }
};
using UnderlyingContainer = std::vector<MyData>;

using MinHeap = std::priority_queue<MyData, UnderlyingContainer, Compare>;

int main() {
    MyData md1{ 5,5 }, md2{ 5,4 }, md3{ 5,3 }, md4{ 5,2 }, md5{ 5,1 };

    MinHeap mh{};

    mh.push(md1); mh.push(md4); mh.push(md3); mh.push(md2); mh.push(md5);

    for (size_t i = 0; i < 5; ++i) {
        std::cout << mh.top();
        mh.pop();
    }
    return 0;
}
于 2021-10-14T18:12:52.967 回答