While I was studying data structures on my own, I became curious about the remove algorithm in a heap tree. The language is C++.
Below is the deletion algorithm for the max heap tree 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 do you put LEFT(largest) instead of largest in i?
If the node fetched from A[heapSize] has a smaller value than the child node when deleting the root node, and the value is exchanged with the larger child node, wouldn’t it be right to put largest in i and compare it with the next children? If it’s written as in the algorithm above, it seems like two level jumps occur, so I’m leaving a question.
I used a translator so the sentences are not smooth. Please understand. Thank you.
전혜지 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.