patternMinor
Why do you need to fill the first element of array when implementing heap?
Viewed 0 times
whytheyouneedarrayheapfirstelementwhenimplementing
Problem
I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value.
For example here the first element is added in constructor.
And visualization here shows that it's also set to something magic.
However, I've seen many examples without the first element. What's the trick and why sometimes it's there and sometimes it's not?
For example here the first element is added in constructor.
And visualization here shows that it's also set to something magic.
However, I've seen many examples without the first element. What's the trick and why sometimes it's there and sometimes it's not?
Solution
It is not some magic element but $-\infty$, which is because this is min-heap, in max-heap it would be $\infty$.
The sole purpose is consistent representation of all elements inserted - it guarantees that the next element can be compared and it will be smaller (or bigger - for appropriate heap type) - just to avoid checking whether inserted element is the first one or not and then it would be compared to existing ones. In this form you avoid something like isEmpty everytime you insert element, so it saves time, redundant function calls and (rather unwanted) conditional statement at the cost of one element called "guardian" or sometimes "terminator" (popular name in the lists where you check for this element instead of some NULL or isEnd).
The sole purpose is consistent representation of all elements inserted - it guarantees that the next element can be compared and it will be smaller (or bigger - for appropriate heap type) - just to avoid checking whether inserted element is the first one or not and then it would be compared to existing ones. In this form you avoid something like isEmpty everytime you insert element, so it saves time, redundant function calls and (rather unwanted) conditional statement at the cost of one element called "guardian" or sometimes "terminator" (popular name in the lists where you check for this element instead of some NULL or isEnd).
Context
StackExchange Computer Science Q#60112, answer score: 5
Revisions (0)
No revisions yet.