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


1 Answer 1


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

  • $\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, 2013 at 6:59
  • $\begingroup$ @Raphael (binary) heaps are always nearly complete binary trees. What do you mean by balancing? $\endgroup$
    – adrianN
    Apr 4, 2013 at 8:24
  • $\begingroup$ @adrianN Yea, forget what I wrote. Thought-knot. $\endgroup$
    – Raphael
    Apr 4, 2013 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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