data-structures - 为什么二叉堆一定是完全二叉树？

Question

堆属性说:

If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Either the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node (this kind of heap is called max heap) or the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap).

但为什么在这个 wiki ，二叉堆必须是 完整 二叉树？在我的印象中，堆属性并不意味着这一点。

Answer 1

根据wikipedia article您提供的，二叉堆必须符合堆属性(如您所讨论的)和形状属性(要求它是一个完整的二叉树)。如果没有 shape 属性，就会失去数据结构提供的运行时优势(即完整性确保在删除元素时有一种定义明确的方法来确定新的根，等等)