An insert adds a new single-node tree to the forest. So a sequence of n inserts into an initially empty heap will simply create n single-node trees. The cost of an insert is clearly O(1). A deleteMin operation removes the node indicated by minPtr. This turns all children of the removed node into roots. We then scan the set of roots (old and new) to find the new minimum, a potentially very costly process. We also perform some rebalancing, i.e., we combine trees into larger ones. The details of this process distinguish different kinds of addressable priority queue and are the key to efficiency. turn now to decreaseKey(h,k) which decreases the key value at a handle h to k. Of course, k must not be larger than the old key stored with h. Write algorithm for given statement
An insert adds a new single-node tree to the forest. So a sequence of n inserts into an initially empty heap will simply create n single-node trees. The cost of an insert is clearly O(1).
A deleteMin operation removes the node indicated by minPtr. This turns all children of the removed node into roots. We then scan the set of roots (old and new) to find the new minimum, a potentially very costly process. We also perform some rebalancing, i.e., we combine trees into larger ones. The details of this process distinguish different kinds of addressable priority queue and are the key to efficiency.
turn now to decreaseKey(h,k) which decreases the key value at a handle h to k. Of course, k must not be larger than the old key stored with h.
Write
Step by step
Solved in 2 steps