C++初学者指南-5.标准库(第二部分)--二叉堆操作

C++初学者指南-5.标准库(第二部分)–二叉堆操作

不熟悉 C++ 的标准库算法？ ⇒ 简介

背景

什么是“堆”

• 一组数据结构（不要和动态存储的内存分区搞混）
• 它们包含可以排序的对象（键）
• 它们根据排序被称为“最大堆”或“最小堆”
• 它们通常用于实现优先队列

支持的操作通常包括：

通常在 O(1)（常数时间）内获取最大值
通常在 O(log N)（对数时间）内移除最大值
通常在 O(1) 或 O(log N) 的时间内插入新键
通常在 O(1) 或 O(log N) 的时间内增加/减少键的变化值

维基百科：“堆”数据结构

二叉最大堆

• 键存储在二叉树的节点中
• 键必须是可排序的，即可比较的。
• 堆属性：父节点的所有子节点的键必须小于或等于父节点的键 P ⇒ 根节点具有最大值
  
  操作的时间复杂度：
• 获取最大值：O(1)（恒定时间）
• 删除最大值：O(log N)（对数时间）
• 插入：O(log N)
• 增加键：O(log N)

二叉树的表示

几乎所有的完全二叉树都可以用数组来表示。

• 树要么由一个节点组成，要么在所有内部层级上必须是完整的。
• 可能没有最右边的叶节点。
  
  

堆操作

C++标准库中的堆

• 二叉最大堆
• 由一个类似数组的容器表示
• 最大值 = 树根 = 数组中的第一个元素
• 键必须可排序（默认使用运算符 <）
  

堆操作 = 是重排（迭代器）范围内元素的算法

• make_heap：将一串键值重新排序成二叉堆
• push_heap：插入新键
• pop_heap：删除最大值

注意：如果你只想要一个优先队列，可以使用专门的标准容器类型 std::priority_queue。

初始化堆

cppreference

std::vector<int> h {1,6,4,2,9,7,8};
// make max heap (default)
make_heap(begin(h), end(h));
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 7 4
// make min heap
make_heap(begin(h), end(h), std::greater<>{});
for (int x : h) { cout << x << ' '; }  // 1 2 4 9 6 7 8

运行示例代码

cppreference

收缩堆

cppreference

std::vector<int> h {1,2,4,9,8,7,6};
make_heap(begin(h), end(h));  // 9 6 8 2 1 4 7
// remove element from heap:
pop_heap(begin(h), end(h));
auto oldmax = h.back();  // oldmax = 9
h.pop_back();
for (int x : h) { cout << x << ' '; }  // 8 6 7 2 1 4

运行示例代码

cppreference

示例：连续收缩

增长堆

cppreference

std::vector<int> h {1,2,4,8,6,7};
make_heap(begin(h), end(h));  // 8 6 7 2 1 4
// add new element to heap:
h.push_back(9);
push_heap(begin(h), end(h));
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 4 7

运行示例代码

cppreference

示例：不断增长

辅助操作

sort_heap (Heap → Sorted Array)

cppreference

cppreference

is_heap

cppreference

cppreference

is_heap_until

cppreference

cppreference

相关内容

“堆”数据结构
标准算法概述
C++标准库算法介绍
标准序列容器（vector、deque、list、…）
标准关联容器（map、set、…）
标准序列视图
cppreference：算法库
cppreference：容器库
视频：什么是 C++ 标准库？
视频：一小时内掌握 105 个 STL 算法 （Jonathan Boccara，2018）
C++ 之旅：容器和算法
算法概述表：

附上原文链接
如果文章对您有用，请随手点个赞，谢谢！^_^