优先级队列数据结构的术语？

Question

我一直在使用一种数据结构，最初的开发人员称之为heap，它用于实现优先级队列。

虽然有很多关于二叉树的文章，但(min/max)堆似乎定义得不太好(细节因实现而异)。

我注意到一些不一定适用于二叉树结构的特性。

• 相同的元素可以多次出现在队列中，而不会造成执行或实现上的复杂性。
• 搜索(虽然可能并且比彻底搜索更快)，但效率不高(因为每个节点的子元素不需要平衡)。
• 由于搜索效率不高，而且可能存在重复搜索，因此删除可能需要存储对node的引用，而不是使用key查找节点(这是二叉树的常见做法)。
• 更改堆中的优先级是微不足道的。，与二叉树在delete+insert最常见的地方相比。 (与二叉树相比，最好的情况更好，最差的情况更糟)

对于符合这些特征的数据结构，是否有更详细的术语？

或者它只是一个碰巧被用作min/max heap的priority-queue

注意，这里有一个指向具有上述特征的民堆的链接。

Answer 1

二进制堆是优先级队列抽象数据结构的具体实现。它之所以流行，是因为它易于实现，内存效率高，而且速度相当快: O(log n)插入，O(log n)移除根(最小在min堆中最小，在max堆中最大)元素。大多数实现还提供了一个peek方法，允许在不删除根元素的情况下查看根元素。

二进制堆不会做任何其他特别好的事情。与您的观察相反，在二进制堆中找到特定项需要顺序扫描。尽管节点是有序的(没有排序)，但顺序并不适合搜索。

二进制堆的典型实现在数组中。由于形状属性(结构可以看作是一个完美的(或完整的)二叉树)，这意味着父和子之间的关系是隐式表示的。项目以宽度第一的顺序存储在数组中。

正如用户Templatety胡枝子在他的回答中指出的那样，二进制堆是一种特定的二叉树，不应该与二进制搜索树混淆，二进制搜索树是专为快速插入和删除项以及按键定位项而设计的。

虽然更改堆中项的优先级或从堆中移除任意项非常容易，但正如您所指出的，问题是查找要操作的项。在典型的二进制堆中，查找要修改的项需要顺序搜索。如果您需要在堆中移动项目的能力，您通常会将二进制与字典或哈希映射结合起来，该字典或哈希映射由项的键索引。值是数组中项的索引。该索引在每次移动项时都会更新。这降低了堆操作的常数因子，但使您能够在O(1)中定位项。

还有一个叫做最小最大堆的东西，它是一种二进制堆，它允许O(1)访问min和max项。该实现非常类似于标准二进制最小堆的实现。

更令人困惑的是，还存在d-ary堆，它是一个每个节点包含两个以上子节点的堆。例如，一个三叉堆每个节点有三个子节点。这些也是在带有隐式子指针的数组中实现的。

还有其他数据结构通常称为堆，但实际上与堆完全无关，只是它们是优先级队列数据结构的不同实现。最流行的似乎是配对堆、斐波纳契堆和二项式堆，所有这些都可以用二叉树实现。(同样，不是二进制搜索树。)

几年前，我在博客中写了一篇关于二进制堆(和d-ary堆)的有一定指导意义的介绍。如果您感兴趣，请查看这一项，它列出了该系列中的所有文章。

Answer 2

我觉得你混淆了二叉树和二叉树。二叉树比其他任何东西都更具有形状--它是一个每个节点最多有两个子节点的树。节点不一定要有值，如果有，就不需要遵守任何特定的规则。

二叉树是一个二叉树，每个节点都持有一个键，每个节点都遵循这样的规则:左侧子树中的所有键都小于该节点的键，而右侧子树中的所有键都大于该节点的键。(有些定义放宽了允许小于或等于的要求，而不是只允许小于等等)

还有许多其他数据结构是由不是BST的二叉树构建的。k-d树存储多维数据。二进制尝试存储位字符串。

因此，我认为这里最好的描述是“二进制堆是完整的、服从堆属性的二叉树，尽管它们具有相同的底层形状(或多或少)，但堆属性与二进制搜索树不一样。”