While I was studying data structures on my own, I became curious about the remove algorithm in a binary heap. Here is the deletion algorithm for a max heap used in the textbook:
remove()
item <- A[1];
heapSize <- heapSize-1;
i <- 2;
while i <= heapSize do
if i < heapSize and A[LEFT(i)] > A[RIGHT(i)]
then largest <- LEFT(i);
else largest <- RIGHT(i);
if A[PARENT(largest)] > A[largest]
then break;
A[PARENT(largest)] <-> A[largest];
i <- LEFT(largest);
return item;
What I’m curious about is the second line from the bottom.
Why does it assign LEFT(largest)
instead of largest
to i
?
If the node at A[PARENT(largest)]
has a smaller value than the child node, and that value is exchanged with the larger child node, shouldn’t largest
be assigned to i
and then compared with the next child? The pseudocode above seems to make two level jumps in one iteration of the loop… How could this be correct?
beginner is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
12