TypechoJoeTheme

鱼一的博客 ◡̈

yuyi

知不可乎骤得,托遗响于悲风
网站页面
标签搜索
文章目录
c++

最大堆or最小堆

在C++标准库中,std::priority_queue默认是一个最大堆,它使用std::less作为其比较函数,这意味着元素总是以非递增的顺序排序。如果你想实现一个最小堆,你可以通过指定一个不同的比较函数来实现,即使用std::greater

以下是如何使用std::priority_queue来实现最大堆和最小堆的示例代码:

最大堆

最大堆已经是std::priority_queue的默认行为。如果你要创建一个存储Node结构的最大堆,你可以像你已经做的那样直接使用它:

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

struct Node {
    int value;
    int idx;
    Node (int v, int i): value(v), idx(i) {}
};

// 使得 priority_queue 默认的比较行为成为最大堆
bool operator < (const Node &n1, const Node &n2) {
    return n1.value < n2.value;
}

int main() {
    // std::priority_queue<Node, std::vector<Node>, std::less<Node>> maxHeap;
    std::priority_queue<Node> maxHeap;
    maxHeap.push(Node(10, 1));
    maxHeap.push(Node(20, 2));
    maxHeap.push(Node(15, 3));

    while (!maxHeap.empty()) {
        Node top = maxHeap.top();
        std::cout << "Max heap top: " << top.value << std::endl;
        maxHeap.pop();
    }
    return 0;
}

最小堆

要创建一个最小堆,你需要使用std::greater作为比较函数,这将使得元素以非递减的顺序被排列:

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // For std::greater

struct Node {
    int value;
    int idx;
    Node (int v, int i): value(v), idx(i) {}
};

// 重载比较运算符用于最小堆
bool operator > (const Node &n1, const Node &n2) {
    return n1.value > n2.value;
}

int main() {
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> minHeap;
    minHeap.push(Node(10, 1));
    minHeap.push(Node(20, 2));
    minHeap.push(Node(15, 3));

    while (!minHeap.empty()) {
        Node top = minHeap.top();
        std::cout << "Min heap top: " << top.value << std::endl;
        minHeap.pop();
    }
    return 0;
}

在上述示例中,std::greater是用来告诉priority_queue如何比较Node类型的对象。注意,为了使用std::greater,你需要重载>运算符而不是<运算符。在这个例子中,>运算符被重载以比较两个Node对象的value成员。

通过这种方式,你可以根据需要灵活地实现最大堆和最小堆。

赞(0)
版权属于:

鱼一的博客 ◡̈

本文链接:

https://yuyi.monster/archives/238/(转载时请注明本文出处及文章链接)

评论 (0)

More Info for me 📱

IP信息

人生倒计时

今日已经过去小时
这周已经过去
本月已经过去
今年已经过去个月