6

维基百科( http://en.wikipedia.org/wiki/Heap_(data_structure) )中给出的堆定义是

在计算机科学中,堆是一种特殊的基于树的数据结构,它满足堆属性:如果 A 是 B 的父节点,则 key(A) 相对于 key(B) 进行排序,并且在整个堆中应用相同的排序. 要么父节点的key总是大于等于子节点的key,最高的key在根节点(这种堆称为max heap),要么父节点的key小于等于子节点的key孩子们(最小堆)

该定义没有说明树是完整的。例如,根据这个定义,二叉树 5 => 4 => 3 => 2 => 1,其中根元素为 5,所有后代都是右孩子,也满足堆属性。我想知道堆数据结构的精确定义。

4

2 回答 2

2

正如其他人在评论中所说:这堆的定义,您的示例树是堆,尽管是退化/不平衡的。树是完整的,或者至少是合理平衡的,对于在树上进行更有效的操作很有用。但是低效的堆仍然是堆,就像不平衡的二叉搜索树仍然是二叉搜索树一样。

请注意,“堆”不是指数据结构,而是指任何满足堆属性或(取决于上下文)特定操作集的数据结构。在堆的数据结构中,最有效的数据结构显式或隐式地保证树是完整的或平衡的。例如,二叉堆根据定义是一棵完全二叉树。

无论如何,你为什么在乎?如果您关心特定操作的特定下限或上限,请说明这些而不是要求堆。如果您讨论的是堆和完整树的特定数据结构,请说明而不是仅仅谈论堆(当然,假设完整性很重要)。

于 2012-10-16T20:10:23.490 回答
0

自从提出这个问题以来,维基百科的定义已经更新:

在计算机科学中,堆是一种专门的基于树的数据结构,它本质上是一棵满足堆属性的几乎完整的1:在最大堆中,对于任何给定的节点 C,如果 P 是 C 的父节点,则P的key(值)大于等于C的key。在min heap中,P的key小于等于C的key。2堆“顶”的节点(没有父节点)称为根节点。

但是,“堆数据结构”实际上是指一系列不同的数据结构,其中还包括:

...这些当然不一定是完整的树。

另一方面,d-ary heap数据结构——包括二叉堆——通常指的是完整的树,因此它们可以在数组中按级别顺序实现,没有间隙:

-ary 堆由一组项目组成,每个项目都有一个与之关联的优先级。这些项目可以看作是完整的二叉树中的节点,按广度优先遍历顺序列出。

于 2021-12-14T20:27:06.787 回答