网站建设需要什么样的内容,科技设计网站有哪些,怎么做网站收录,网站优化怎样做外链C初学者指南-5.标准库(第二部分)–二叉堆操作 文章目录 C初学者指南-5.标准库(第二部分)--二叉堆操作背景什么是“堆”二叉最大堆二叉树的表示 堆操作C标准库中的堆初始化堆收缩堆增长堆 辅助操作sort_heap (Heap → Sorted Array)is_heapis_heap_until 相关内容 不熟悉 C 的标…C初学者指南-5.标准库(第二部分)–二叉堆操作 文章目录 C初学者指南-5.标准库(第二部分)--二叉堆操作背景什么是“堆”二叉最大堆二叉树的表示 堆操作C标准库中的堆初始化堆收缩堆增长堆 辅助操作sort_heap (Heap → Sorted Array)is_heapis_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::vectorint 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::vectorint 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::vectorint 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 Boccara2018 C 之旅容器和算法 算法概述表
附上原文链接 如果文章对您有用请随手点个赞谢谢^_^
