Pointer-based binary heap implementation
Posted
by
Derek Chiang
on Stack Overflow
See other posts from Stack Overflow
or by Derek Chiang
Published on 2013-11-01T03:43:43Z
Indexed on
2013/11/01
3:53 UTC
Read the original article
Hit count: 262
Is it even possible to implement a binary heap using pointers rather than an array? I have searched around the internet (including SO) and no answer can be found.
The main problem here is that, how do you keep track of the last pointer? When you insert X into the heap, you place X at the last pointer and then bubble it up. Now, where does the last pointer point to?
And also, what happens when you want to remove the root? You exchange the root with the last element, and then bubble the new root down. Now, how do you know what's the new "last element" that you need when you remove root again?
© Stack Overflow or respective owner