当前位置：首页 > news >正文

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

news 来源：原创 2024/9/20 7:23:45

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

文章目录

C++初学者指南-5.标准库(第二部分)--二叉堆操作
- 背景
- - 什么是“堆”
  - 二叉最大堆
  - 二叉树的表示
- 堆操作
- - C++标准库中的堆
  - 初始化堆
  - 收缩堆
  - 增长堆
- 辅助操作
- - sort_heap (Heap → Sorted Array)
  - is_heap
  - is_heap_until
- 相关内容

不熟悉 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