Menu
Here's my rough sketch of the beginning of a heap with arbitrary values
0 1 2 3 4 5 6 7 8 9 ...
[-] [10] [14] [15] [22] [21] [24] [23] [44] [30] ...
Why must the element in array[0] always be set to null?
Or why is it that we are not supposed to use it?
810
BinaryHeap and it starts the heap implementation from index 1.
However, a heap is not a sorted structure; it can be regarded as being partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be interspersed with removals of the root node.
A Min Heap Binary Tree is a Binary Tree where the root node has the minimum key in the tree.
For a random heap, and for repeated insertions, the insertion operation has an average-case complexity of O(1).
There are several ways to represent a binary heap as an array.
There is a way whereby element zero is used; there is also a way whereby element zero is not used:
n are elements 2n+1 and 2n+2;n are elements 2n and 2n+1.Neither is more "correct" than the other. The former is a better fit for programming languages that use zero-based arrays, whereas the latter is a better fit for languages with one-based arrays.
It would appear that you've encountered an implementation that uses the second approach. Since the language in question, Java, uses zero-based arrays, element zero exists but is not being used.
109
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
