堆数据结构的准确定义是什么？

Question

在计算机科学中，堆是一种专门的基于树的数据结构，它满足堆属性：如果 A 是 B 的父节点，则 key(A) 相对于 key(B) 进行排序，并且在整个堆中应用相同的排序。要么父节点的键总是大于或等于子节点的键，并且最高键在根节点（这种堆称为最大堆），要么父节点的键小于或等于孩子们（最小堆）

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

Answer 1

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

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

无论如何，你为什么要关心？如果您关心特定操作的特定下限或上限，请说明它们而不需要堆。如果您讨论堆和完整树等特定数据结构，请说明这一点，而不仅仅是谈论堆（当然，假设完整性很重要）。