4
$\begingroup$

I have a heap where both child nodes of the root are 10, and I'd like to perform an operation to remove the min value 9.

I proceed to replacing the root with its next of kin, 18. However when I bubble down, I am unsure of which direction to take.

enter image description here

$\endgroup$
2
$\begingroup$

Picking either should work. The heap property (assuming you have changed it to mean parent $\le$ children) will not be violated.

$\endgroup$
  • $\begingroup$ I'm thinking that one should randomise the decision for the sake of balancing, but I'm not sure that's necessary. $\endgroup$ – Raphael Apr 4 '13 at 6:59
  • $\begingroup$ @Raphael (binary) heaps are always nearly complete binary trees. What do you mean by balancing? $\endgroup$ – adrianN Apr 4 '13 at 8:24
  • $\begingroup$ @adrianN Yea, forget what I wrote. Thought-knot. $\endgroup$ – Raphael Apr 4 '13 at 8:38

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.