B堆
B堆（）是一个用来保证子树在一个内存页的二叉堆。这样可以在使用虚拟内存时减少访问很大堆时内存页的访问。传统的实现中，元素位置的映射（几乎）每一级都放在不同的内存页中。 也有其他非常高效实用虚拟内存和缓存的堆的变种，例如、k堆、和van Emde Boas树。 参见 参考文献 外部链接 实现： https://web.archive.org/web/20120722102205/https://www.varnish-cache.org/…
标签：#堆
共 10 篇文章
配对堆
配对堆（）是一种实现简单、均摊复杂度优越的堆数据结构，由邁克爾·弗雷德曼、罗伯特·塞奇威克、丹尼爾·斯萊托、羅伯特·塔揚于1986年发明。 配对堆是一种多叉树，并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆最小生成树算法等算法，配对堆是一个更优的选择，且支持以下操作（假设该堆是最小堆）： find-min（查找最小值）：返回堆顶。 merge（合并）：比较两个堆顶，将堆顶较大的堆设为另一个的孩子。 insert（插入）：创建一…
堆積
堆（）是计算机科学中的一種特別的完全二叉树。若是滿足以下特性，即可稱為堆積：「給定堆積中任意節點P和C，若P是C的父節點，那麼P的值會小於等於（或大於等於）C的值」。若父節點的值恆小於等於子節點的值，此堆積稱為最小堆積（）；反之，若父節點的值恆大於等於子節點的值，此堆積稱為最大堆積（）。在堆積中把根節點（）稱為堆積頂（top），而底層最靠右的節點稱為堆積底（bottom）。 堆積始於在1964年發表的堆積排序（），當時他提出了二元堆積樹…
斜堆
斜堆（）是左偏树的一个变种。斜堆是一棵保持堆有序的二叉树，但是它不满足左偏性质，或者说斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说，所有的左偏树都是斜堆，但反之不然。 定义 仅有一个节点的树为斜堆； 两个斜堆合并的结果仍为斜堆。 合并操作 斜堆合并操作的递归合并过程和左偏树完全一样。假设我们要合并 A 和 B两个斜堆,且 A 的根节点比 B 的根节点小,我们只需要把 A 的根节点作为合并后新斜堆的根节点…
左偏树
左偏树（），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。 不同于斜堆合并的,左偏堆的合并操作的为 O(log n)，而完全二叉堆为 O(n)，所以左偏堆适合基于合并操作的情形。 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。 定义 左偏树是…
二项堆
在计算机科学中，二项堆（）是一种类似于二叉堆的堆结构。与二叉堆相比，其优势是可以快速合并两个堆，因此它属于可合并堆（）抽象数据类型的一种。 二项树 二项树递归定义如下： 度数为0的二项树只包含一个節点 度数为k的二项树有一个根節点，根節点下有k个子女，每个子女分别是度数分别为k-1, k-2, ..., 2, 1, 0的二项树的根 度数为k的二项树共有2^k个節点，高度为k。在深度d处有\tbinom k d（二项式系数）个節点。 度数…
斐波那契堆
斐波那契堆（）是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能，可用于实现合并优先队列。不涉及删除元素的操作有 O(1) 的平摊时间。 Extract-Min和Delete的数目和其它相比，较小时效率更佳。稠密图每次decrease key只要 O(1) 的平摊时间，和二项堆的 O(\log n) 相比是巨大的改进。 斐波纳契堆于1984年由邁克爾·弗雷德曼与罗伯特·塔扬提出，1987年公开发表。名字来源于运行时分析使用的斐波那…
二叉堆
二叉堆（）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是保持固定的序关系于任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆。 当父節点的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父節点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。 存储 二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点…
Brodal队列
在计算机科学中，Brodal队列是一种堆、优先队列数据结构。该数据结构有很优的最劣时间复杂度：O(1)插入、找到最小值、合并或单点减少，O\left (\mathrm{log}\left (n\right )\right )删除元素。这是第一种非均摊实现该复杂度的堆。其得名于发明者Gerth Stølting Brodal。 虽然该结构具有优越的渐进复杂度，Brodal本人表示它“很复杂”，“不适合实践”。Brodal和Okasaki也…
最大—最小堆
最大堆示例]] 最小堆示例]] 最小—最大堆（Min-Max Heap）是最大层和最小层交替出现的二叉树，即最大层结点的子節點属于最小层，最小层结点的子節點属于最大层。以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。 介绍 最大堆和最小堆是二叉堆的两种形式。 最大堆：根结点的键值是所有堆结点键值中最大者的堆。 最小堆：根结点的键值是所有堆结点键值中最小者的堆。 而最大—最小堆集结了最大…