本文主要是讲解堆排序的原理和具体实现方法。

1 堆排序

1.1 堆排序的原理

1.2 堆排序的应用：topk问题

堆排序：堆排序最典型的场景就是topK问题

使用堆实现top-k问题的技巧：
获取最大的K个元素，使用小顶堆(优先剔除较小的元素)。
获取最小的K个元素，使用大顶堆(优先剔除较大的元素)。

TopK 示例，来源【前 K 个高频元素(LCR060)】，实现原理：

  1. 先使用K个元素构建一个小顶堆。
  2. 然后将堆顶元素从堆中删除，然后将新元素插入堆中。
  3. 重复这个过程，直到遍历完所有元素。
  4. 当遍历完所有元素以后，留在堆中的元素就是最大K个元素。（因为较小的元素都被剔除了。）
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

    static bool cmp(pair<int, int> left, pair<int, int> right) {
        return left.second > right.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> num_cnt;
        for (auto& item : nums) {
            num_cnt[item]++;
        }

        // init priority_queue
        priority_queue<pair<int, int>, vector<pair<int,int>>, decltype(&cmp)> little_heap(cmp);
        for (auto& [num, cnt] : num_cnt) {
            if (little_heap.size() < k) {
                little_heap.emplace(num, cnt);
            } else {
                if (little_heap.top().second < cnt) {
                    little_heap.pop();
                    little_heap.emplace(num, cnt);
                }
            }
        }

        vector<int> res;
        while (!little_heap.empty()) {
            res.emplace_back(little_heap.top().first);
            little_heap.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }

1.3 大顶堆实现降序序列

使用优先级队列实现大顶堆,默认就是大顶堆。
大顶堆也可以用来排序：大顶堆排序的结果为降序序列，
堆出列时，先弹出顶部的元素，而顶部的元素最大，所以的得到序列就是降序的。

1
2
3
4
5
6
7
8
9

vector<int> vec = {1,8,5,6,3,4,0,9,7,2};
std::priority_queue<int> pri_que;
for (int val : vec) {
    pri_que.push(val);
}

// 或者自定义比较函数实现
std::vector<int> vec = {3, 1, 4, 1, 5};
std::priority_queue<int> big_heap(std::less<int>(), vec);

1.4 小顶堆实现升序序列

使用优先级队列实现小顶堆需要自定义比较函数。小顶堆的排序结果为升序序列。
优先级队列中的比较函数的含义：顶部元素和尾部元素的比较结果。
例如：小顶堆中比较函数是greater的原因是，只有顶部元素比尾部元素大，才需要交换。

1
2
3

 // 使用优先级队列实现小顶堆的方法
std::vector<int> vec = {3, 1, 4, 1, 5};
std::priority_queue<int> little_heap(vec, std::greater<int>());