巧用 STL 容器构建堆

[toc]

红黑树

什么是红黑树

set/multiset 实现最大堆

在 STL 中，set 和 multiset 是基于红黑树实现的。

• Sets are usually implemented as red-black trees.
• Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity.

Code Example

#include <iostream>
#include <ostream>
#include <set>

int main() {
  // Initialize a set.
  // Compare parameter is default to std::less<Key>.
  std::set<int> min_s;
  min_s.insert(1);
  min_s.insert(3);
  min_s.insert(2);
  min_s.insert(5);
  min_s.insert(4);
  min_s.insert(-1);

  std::cout << "min value of set container is " << *min_s.begin() << std::endl;
  std::cout << "max value of set container is " << *min_s.rbegin() << std::endl;

  // Compare parameter is default to std::greater<Key>.
  std::set<int, std::greater<int>> max_s;
  max_s.insert(1);
  max_s.insert(3);
  max_s.insert(2);
  max_s.insert(5);
  max_s.insert(4);
  max_s.insert(-1);

  std::cout << "max value of set container is " << *max_s.begin() << std::endl;
  std::cout << "min value of set container is " << *max_s.rbegin() << std::endl;

  // Initialize a multiset.
  std::multiset<int, std::greater<int>> max_ms;
  max_ms.insert(1);
  max_ms.insert(3);
  max_ms.insert(2);
  max_ms.insert(5);
  max_ms.insert(4);
  max_ms.insert(-1);

  std::cout << "max value of multiset container is " << *max_ms.begin()
            << std::endl;
  std::cout << "min value of multiset container is " << *max_ms.rbegin()
            << std::endl;

  return 0;
}

输出结果如下

min value of set container is -1
max value of set container is 5
max value of set container is 5
min value of set container is -1
max value of multiset container is 5
min value of multiset container is -1

参考 <剑指 offer> 面试题 40 — 最小的 k 个数

基于 STL 的函数 push_heap、pop_heap 和 vector 实现堆

参考 <剑指 offer> 面试题 41 — 数据流中的中位数

更改记录

2023.04.02 搭建架子，写出 set 版本。