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.
$\begingroup$
$\endgroup$
asked Apr 4, 2013 at 2:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$– adrianNApr 4, 2013 at 8:24
-
$\begingroup$ @adrianN Yea, forget what I wrote. Thought-knot. $\endgroup$– Raphael ♦Apr 4, 2013 at 8:38