数据结构:堆

若有树,任取其某一局部,都满足根节点大于等于子节点,则这个树是一个最大堆。同理有最小堆。

如何建堆

建立小根堆的例子:(下面用方括号指出调整的根)

建立堆的过程,颇有分形艺术的感觉。首先我们跳过最末元素 49, 27, 13, 76因为它们是叶子节点,对于每一个,自身已经是堆——因为没有子节点。因此调整的起点是第 $\lfloor n / 2\rfloor$ 个元素,也即 0 起的 v[n/2 - 1]

 1let v = [49, 38, 65, 97, 76, 13, 27, 49]
 2/*
 3      49
 4     /   \
 5   38     65
 6  /\       / \
 7 [97] 76  13  27 // 调整的起点是 97
 8 /
 949
10*/

目标是将 97 的子树(

  97
  /
49

)变成堆:

 1/*
 2      49
 3     /  \
 4   38    [65] // 然后我们处理 97 的前一个元素 65
 5  /\     / \
 6 49 76  13  27
 7 /
 897
 9
10      49
11     /  \
12   [38]    13 // 处理再往前一个元素
13  /\     / \
14 49 76  65  27
15 /
1697
17
18      [49] // 处理再往前一个元素
19     /  \
20   38    13
21  /\     / \
22 49 76  65  27
23 /
2497
25
26      13
27     /  \
28   38    [49] // 如果与子节点发生了交换,那么子节点所在树要重新调整
29  /\     / \
30 49 76  65  27
31 /
3297
33
34
35      13
36     /  \
37   38    27
38  /\     / \
39 49 76  65  49
40 /
4197
42
43完成,构成了小根堆,并找出了最小元素 13.
44
45*/

参考此处

将无序序列顺存,当作完全二叉树。

所有叶子已经是堆(无子节点,相当于子节点是 0),从最后一个非叶子进行调整。

  • 如何找到最末非叶子?就是 N/2 向下取整。

  • 调整哪里?以最末非叶为根的子树调整。

  • 如何调整?挑选儿子其中更小的,与自己比较然后交换!(建立小根堆,则交换使得根更小)

    • 如果交换了,那么要检查交换后的子节点的树,可能需要重新调整。
  • 调整完呢?调整之后的最末非叶子!(N/2 - 1

如此处理直到根节点搞定。一轮之后,根将会变成最小元素。

如何调整堆

拿出 H 的根(输出),然后把 last(H) 作为新根。

比较新根的左右孩子,同其中更小的交换。交换之后它的孩子变了,如果还有孩子,就继续执行这一步。

堆排序

如何利用建堆实现堆排序?前面的例子看出,堆排序能够选择出最小的元素。那么对于剩余的元素,再次进行堆排序,可以选择出第二小的元素。

  • 初始堆化的时间:$O(n)$

  • 一次堆化的时间(插入性能):$O(\log n)$

  • n-1 次循环时间(排序性能):$O(n\log n)$

因此时间复杂度为 $O(n) + O(n \log n ) = O(n \log n)$

练习

912. 排序数组 - 力扣(LeetCode) (leetcode-cn.com)

参考实现:

 1#include <debug.h>
 2
 3void adjust(vector<int> &v, int bound, int i) {
 4  // 子节点索引
 5  int i_left = 2 * i + 1;
 6  int i_right = i_left + 1;
 7  // 选出比根大的子节点
 8  int i_max = i;
 9  i_max = i_left < bound && v[i_left] > v[i_max] ? i_left : i_max;
10  i_max = i_right < bound && v[i_right] > v[i_max] ? i_right : i_max;
11  if (i_max != i) {
12    // 让小的靠根
13    swap(v[i_max], v[i]);
14    // 调整变化后的子树
15    adjust(v, bound, i_max);
16  }
17}
18
19void heap_sort(vector<int> &v) {
20  // 构建大根堆
21  int n = v.size();
22  for (int i = n / 2 - 1; i >= 0; i--) {
23    adjust(v, n, i);
24  }
25  // 选择排序
26  for (int i = n - 1; i != 0; i--) {
27    swap(v[0], v[i]);
28    adjust(v, i, 0);
29  }
30}
31
32class Solution {
33public:
34  vector<int> sortArray(vector<int> &nums) {
35    vector<int> ret(nums);
36    heap_sort(ret);
37    return ret;
38  }
39};
40
41int main(int argc, char const *argv[]) {
42  Solution s;
43  vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
44  auto sorted = s.sortArray(arr);
45  print_vec(sorted);
46  return 0;
47}

优先队列

优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用****来实现。

优先队列至少需要支持下述操作:

  • 插入带优先级的元素(insert_with_priority)

  • 取出具有最高优先级的元素(pull_highest_priority_element)

  • 查看最高优先级的元素(peek):O(1) 时间复杂度

其它可选的操作:

  • 检查优先级高的一批元素

  • 清空优先队列

  • 批插入一批元素

  • 合并多个优先队列

  • 调整一个元素的优先级

——优先队列

我们先看看 C++ 自带的优先队列怎么用。

C++ 优先队列

头文件:#include<queue>

下面定义一个升序优先队列。队列顶部是最小的。

1priority_queue <int,vector<int>,greater<int> > q_asc;
2// 送入值,送的过程中自动排好序
3q_asc.push(...);
4// 取出队中最小值
5auto min_of_q = q_asc.top();

样例(P215 解):

 1#include <debug.h>
 2#include <queue>
 3class Solution {
 4public:
 5  int findKthLargest(vector<int> &nums, int k) {
 6    priority_queue<int, vector<int>, greater<int>> q;
 7    for (auto num : nums) {
 8      // 随便送入 k 个数字到 q
 9      if (q.size() != k) {
10        q.push(num);
11      }
12      // 然后把最小的换走,剩下 k 个最大的
13      else {
14        auto min_of_q = q.top();
15        if (num > min_of_q) {
16          // 置换
17          q.pop();
18          q.push(num);
19        }
20      }
21    }
22    return q.top();
23  }
24};
25
26int main(int argc, char const *argv[]) {
27  Solution s;
28  vector<int> v = {3, 2, 3, 1, 2, 4, 5, 5, 6};
29  cout << s.findKthLargest(v, 4) << endl;
30  return 0;
31}

练习

215. 数组中的第K个最大元素 - 力扣(LeetCode) (leetcode-cn.com)

最近发布

要查看全部文章,请点击右上角“归档”,下面是最近发布的几篇日志