8.22 Show all the steps of the algorithm for replacing key 5 with 18 in the heap
ID: 3554315 • Letter: 8
Question
8.22
Show all the steps of the algorithm for replacing key 5 with 18 in the heap of figure 8.3 Draw an example of a heap whose keys are all the odd numbers from 1 to 59 (with no repeats), such that thee insertion of an entry with key 32 would se up-hcap bubbling to proceed all the way up to a child of the replacing that child's key with 32). Complete Figure 8.9 by showing all the steps of the in-place heap-sort algorithm. Show both the array and the associated heap at the end of each step. Give a pseudo-code description of a nonrecursive in-place heap-sort algorithm. A group of children want to play a game, called Unmonopoly, where in each turn the player with the most money must give half of his/her money to the player with the least amount of money. What data structured) should be used to play this game efficiently? Why?Explanation / Answer
Basic idea is to build the heap from the bottom up Although the algorithm is naturally recursive, I will describe it iteratively.
1. Make (n+1)/2 single item heap trees, Note (n-1)/2 items still in reserve.
2. Merge pairs of heaps single item heaps by adding an item from the reserve. Note (n+1)/4 heaps now.
3. Merge pairs of three item heaps by adding item from the reserve. Note (n+1)/8 heaps
:
:
Do this h = lg(n + 1) times, the height of the tree.
Illustrate iteratively 15 keys page 317
Recursive Algorithm for BottomUpHeap(S)
input: Sequence S with n = 2h - 1 keys
Output: Heap T storing the keys of S.
if S empty then return empty heap
Remove the first key, k, from S.
// Note k will become root of new Tree
Split S into S1 and S2 each of size (n-1)/2
// recursive calls
T1 = BottomUpHeap(S1)
T2 = BottomUpHeap(S2)
Create binary tree T with
root storing k,
T1 left subtree and T2 right subtree
Perform Bubble down from root of T
return T
Cost is O(n) is not immediately apparent form the algorithm.
The proof can be demonstrated visually. The worst case cost for each recursive call of the algorithm is height of the current tree, T, because of the bubbling. We will determine the total cost by delineating the cost of all the bubble down operations. We associate the path to the successor in-order node (first down right then down left) with the root node. This a possible bubbling path. The total time, form all the recursive calls, is the total number of associated paths, which is O(n).
Although the heap is constructed in O(n), removing min from the heap and reconstructing the order sequence still takes O( n lg n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.