自定义比较器与堆操作详解——打造专属排序规则

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

struct Student {
    string name;   // 姓名
    int age;       // 年龄

    // 重载小于号：让年龄大的同学被视作“小于”年龄小的
    // 注意：priority_queue 默认是最大堆，它会认为“大”的优先级高
    // 所以这里我们让 age 大的返回 true（即“我比你小”，从而被堆顶优先弹出）
    bool operator<(const Student& other) const {
        return age < other.age;   // 年龄大 > 年龄小，所以年龄大的在堆顶
    }
};

int main() {
    priority_queue<Student> pq;  // 默认使用 less<Student>，调用 operator<
    pq.push({"Alice", 12});      // 姓名 Alice，年龄 12
    pq.push({"Bob", 10});        // 姓名 Bob，年龄 10
    pq.push({"Charlie", 15});    // 姓名 Charlie，年龄 15

    while (!pq.empty()) {
        Student top = pq.top();
        cout << top.name << " " << top.age << endl;
        pq.pop();
    }
    return 0;
}
// 输出（年龄从大到小）：
// Charlie 15
// Alice 12
// Bob 10

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

struct Student {
    string name;
    int age;
};

// 定义一个函数对象：按年龄从小到大（即最小堆）
struct CompareByAgeAsc {
    // 括号运算符：判断 a 的优先级是否低于 b
    // 如果返回 true，表示 a 比 b 优先级低（a 应该排在 b 后面）
    bool operator()(const Student& a, const Student& b) const {
        return a.age > b.age;   // 年龄大的优先级低 → 年龄小的优先级高 → 最小堆
    }
};

int main() {
    // 模板参数：元素类型、底层容器、比较器类型
    priority_queue<Student, vector<Student>, CompareByAgeAsc> pq;
    pq.push({"Alice", 12});
    pq.push({"Bob", 10});
    pq.push({"Charlie", 15});

    while (!pq.empty()) {
        auto s = pq.top();
        cout << s.name << " " << s.age << endl;
        pq.pop();
    }
    return 0;
}
// 输出（年龄从小到大）：
// Bob 10
// Alice 12
// Charlie 15

#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;

struct Student {
    string name;
    int age;
};

int main() {
    // auto 推导 lambda 类型
    auto cmp = [](const Student& a, const Student& b) {
        return a.age > b.age;      // 最小堆
    };
    // 注意：模板参数用 decltype(cmp)，并传入 lambda 对象
    priority_queue<Student, vector<Student>, decltype(cmp)> pq(cmp);
    pq.push({"Alice", 12});
    pq.push({"Bob", 10});
    pq.push({"Charlie", 15});

    while (!pq.empty()) {
        auto s = pq.top();
        cout << s.name << " " << s.age << endl;
        pq.pop();
    }
    return 0;
}
// 同样输出最小堆

#include <iostream>
#include <algorithm>   // for heap functions
#include <vector>
using namespace std;

int main() {
    vector<int> v = {30, 10, 50, 20, 40};

    // 1. 建堆（最大堆）
    make_heap(v.begin(), v.end());
    cout << "初始堆: ";
    for (int x : v) cout << x << " ";  // 堆顶是最大值 50
    cout << endl;

    // 2. 插入新元素：先添加到最后，再 push_heap
    v.push_back(45);
    push_heap(v.begin(), v.end());
    cout << "插入45后: ";
    for (int x : v) cout << x << " ";  // 堆顶现在是 50
    cout << endl;

    // 3. 弹出堆顶元素（移到末尾，然后手动删除）
    pop_heap(v.begin(), v.end());   // 50 被移到 v.back()
    int max_val = v.back();         // 取出最大值
    v.pop_back();                   // 真正删除
    cout << "弹出最大元素 " << max_val << " 后: ";
    for (int x : v) cout << x << " ";
    cout << endl;

    // 4. 堆排序（升序）
    sort_heap(v.begin(), v.end());  // 变成升序（注意：会破坏堆性质）
    cout << "堆排序后: ";
    for (int x : v) cout << x << " ";  // 输出: 20 30 40 45 (假设之前元素)
    cout << endl;

    return 0;
}

vector<int> v = {30, 10, 50, 20, 40};
make_heap(v.begin(), v.end(), greater<int>());
// 现在 v 是最小堆，堆顶是 10
// 后续的 push_heap、pop_heap 也都要传 greater<int>()

import heapq

# 存储 (优先级, 任务)
heap = []
heapq.heappush(heap, (3, "写作业"))
heapq.heappush(heap, (1, "紧急任务"))
heapq.heappush(heap, (2, "看书"))

while heap:
    print(heapq.heappop(heap))
# 输出：(1, '紧急任务'), (2, '看书'), (3, '写作业')

heapq.heappush(heap, (-10, "紧急"))

import heapq

class Task:
    def __init__(self, name, priority):
        self.name = name          # 任务名
        self.priority = priority  # 优先级（数值越大越紧急）

    def __lt__(self, other):
        # 我们想让优先级大的任务先弹出（即认为“大”的反而“小”）
        # 因为 heapq 是最小堆，__lt__ 返回 True 表示 self 比 other “小”，先弹出
        return self.priority > other.priority

    def __repr__(self):
        return f"{self.name}({self.priority})"

tasks = [Task("吃饭", 5), Task("睡觉", 2), Task("紧急", 10)]
heapq.heapify(tasks)
while tasks:
    print(heapq.heappop(tasks))
# 输出（按优先级从大到小）：
# 紧急(10)
# 吃饭(5)
# 睡觉(2)