堆數據結構的精確定義是什麼？

Question

在維基百科中給出的堆的定義（http://en.wikipedia.org/wiki/Heap_(data_structure)）是

在計算機科學中，堆是一個專門的基於樹的數據結構 滿足堆屬性：如果A是B的父節點然後 密鑰（A）相對於密鑰（B）被排序，相同的排序 適用於整個堆。父節點的密鑰總是大於或等於子節點的密鑰 ，並且根節點中的最高密鑰爲 （這種堆稱爲最大堆），或者父節點的密鑰小於或等於 （最小 堆）

該定義沒有說明樹是完整的。例如，根據這個定義，二元樹5 => 4 => 3 => 2 => 1，其中根元素爲5，並且所有後代都是正確的子元素也滿足堆性質。我想知道堆數據結構的準確定義。

Answer 1

正如其他人在評論中所說：是堆的定義，而您的示例樹是堆，儘管是退化/不平衡的堆。樹是完整的，或者至少是合理平衡的，對於樹上更高效的操作是有用的。但是低效的堆仍然是一堆，就像不平衡的二叉搜索樹仍然是二叉搜索樹。

請注意，「堆」並不是指數據結構，它指的是任何滿足堆屬性或（取決於上下文）某一組操作的數據結構。在堆中的數據結構中，最有效的數據結構明確或隱含地保證樹完整或有點平衡。例如，二進制堆根據定義是一個完整的二叉樹。

無論如何，你爲什麼在意？如果您關心特定操作的特定下限或上限，請說明這些操作，而不是需要堆。如果你討論具體的數據結構是堆和完整的樹，說明，而不是隻說堆（當然，假設完整性很重要）。