A full binary tree is not necessarily well-balanced. For instance, this is a full binary tree:
1
/ \
2 3
/ \
4 5
/ \
6 7
/ \
8 9
/ \
10 11
In general, a full binary tree where any right child is also a leaf, has a height that is O(????), more precisely, (????−1)/2. This will be problematic for heaps, which rely on the tree being well balanced to keep its insert/delete operations within a time complexity of O(log????).
Secondly, full binary trees always have an odd number of nodes (except when they are empty). This already makes them impractical, as obviously heaps should be able to have even sizes too.
Other alternative
However, binary heaps do not have to be complete binary trees. That is only required when their implementation is the well-known array-based one. But one could also implement a binary heap with an AVL tree, which is not necessarily a complete binary tree, but which still keeps the tree balanced and will have the same time complexities for the heap operations. But since the overhead of the pointer management is larger than working with indices in an array, the array representation leads to faster operations.
Why complete?
The choice for a complete binary tree comes into play when the implementation is array-based and not an explicit node-pointer representation. When you fill an array with values in level-order, and don't allow for gaps in the array (unused slots), then it follows that the tree is complete. Although you could imagine an array that allows for gaps, this would be an inferior choice, as it wastes space, with no gain to compensate for it.
First of all, it is not possible to create a heap structure without it being tightly packed. Every item in the array has a position in the binary tree, and this position comes from the array index.
Also, it has several advantages like the following:
Some operations of the heap have a time complexity of O(lgn) where n is the height of the tree, keeping the height of the tree at a minimum allows us to keep the time required for these operations at a minimum.
All the items of the complete binary tree are stored in a contiguous manner in an array so random access is possible by keeping the heap as a complete binary tree
The completeness ensures that there is a well-defined and efficient way to determine the new root when an element is removed, not using a complete structure would mean losing this advantage (which is why you should use heap in the first place).
发布评论
评论（2）
完整的二进制树堆？
a 完整的二进制树不一定要良好。例如，这是一棵完整的二进制树：
一般而言，一棵完整的二进制树，其中任何右孩子也是叶子，其高度是o（
Full binary trees for heaps?
A full binary tree is not necessarily well-balanced. For instance, this is a full binary tree:
In general, a full binary tree where any right child is also a leaf, has a height that is O(????), more precisely, (????−1)/2. This will be problematic for heaps, which rely on the tree being well balanced to keep its insert/delete operations within a time complexity of O(log????).
Secondly, full binary trees always have an odd number of nodes (except when they are empty). This already makes them impractical, as obviously heaps should be able to have even sizes too.
Other alternative
However, binary heaps do not have to be complete binary trees. That is only required when their implementation is the well-known array-based one. But one could also implement a binary heap with an AVL tree, which is not necessarily a complete binary tree, but which still keeps the tree balanced and will have the same time complexities for the heap operations. But since the overhead of the pointer management is larger than working with indices in an array, the array representation leads to faster operations.
Why complete?
The choice for a complete binary tree comes into play when the implementation is array-based and not an explicit node-pointer representation. When you fill an array with values in level-order, and don't allow for gaps in the array (unused slots), then it follows that the tree is complete. Although you could imagine an array that allows for gaps, this would be an inferior choice, as it wastes space, with no gain to compensate for it.
首先，不可能创建一个堆结构，而不会被紧密包装。阵列中的每个项目都有二进制树的位置，并且此位置出现从阵列索引。
另外，它具有多个优点如下：
堆的某些操作具有
o（lgn）的时间复杂性，其中n是树的高度，将树的高度保持在最低限度，使我们能够将这些操作所需的时间保持在最低。完整二进制树的所有项目都以连续的方式存储在数组中，因此可以通过将堆作为完整的二进制树
来随机访问
来确保有明确且有效的方法来确定确定该量的完整性。当删除元素时，不使用完整的结构将意味着失去此优势（这就是为什么您应该首先使用堆）。
First of all, it is not possible to create a heap structure without it being tightly packed. Every item in the array has a position in the binary tree, and this position comes from the array index.
Also, it has several advantages like the following:
Some operations of the heap have a time complexity of
O(lgn)wherenis the height of the tree, keeping the height of the tree at a minimum allows us to keep the time required for these operations at a minimum.All the items of the complete binary tree are stored in a contiguous manner in an array so random access is possible by keeping the heap as a complete binary tree
The completeness ensures that there is a well-defined and efficient way to determine the new root when an element is removed, not using a complete structure would mean losing this advantage (which is why you should use heap in the first place).