3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Here is how adding to heap looks like without the first element: gist.github.com/ro31337/bedeb9b3edffa96b2338328e82426454 Where is conditional statement at the cost of one element here? Source taken from habrahabr.ru/post/112222 . How it will be different with the first element? $\endgroup$ – Roman Pushkin Jun 28 '16 at 23:37
  • $\begingroup$ $i > 0 &&$, to lazy eval possibility of the non-existence of two compared elements. With the guardian the check will not be present and the parent will be the guardian. $\endgroup$ – Evil Jun 28 '16 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.