为什么二叉堆必须是一个完整的二叉树？ [英] Why does a Binary Heap has to be a Complete Binary Tree?

问题描述

堆属性说：

如果A是B的父节点，则节点A的密钥以
相对于节点B的密钥，具有相同的排序应用于
的堆。父节点的密钥总是大于或等于子节点的
，并且根节点中的最高密钥
（这种堆称为最大堆）或父节点的密钥是
小于或等于孩子的最低键是
根节点（最小堆）。

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 中，二进制堆必须是完成二进制树？ Heap Property并不意味着我的印象。

But why in this wiki, the Binary Heap has to be a Complete Binary Tree? The Heap Property doesn't imply that in my impression.

推荐答案

根据维基百科文章，二进制堆必须符合heap属性（如你所讨论的）和shape属性（它要求它是一个完整的二叉树）。没有shape属性，就会失去数据结构所提供的运行时优势（即，完整性确保在删除某个元素时有一个很好的定义方式来确定新的根）等等。

According to the wikipedia article you provided, a binary heap must conform to both the heap property (as you discussed) and the shape property (which mandates that it is a complete binary tree). Without the shape property, one would lose the runtime advantage that the data structure provides (i.e. the completeness ensures that there is a well defined way to determine the new root when an element is removed, etc.)

这篇关于为什么二叉堆必须是一个完整的二叉树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！