Build a MAX-Heap that would result from the following numbers in the given order. 15, 25, 10, 33, 55, 47, 82, 90, 18 Draw the final heap using two formats: a tree and an array like Figure 6.31 in Page 336 in the textbook. You must build the heap using the algorithm in Page 333 in the textbook. Your final MAX-Heap as a tree: Your final MAX-Heap as an array:

6.5 Heaps and Priority Queues 333 FIGURE 6.2 Inserting 8 Into a Heap FIGURE 6.22 Swapping 8 and 66 FIGURE 6.2 Swapping 8 and 29 6 6 6 18 18 29 18 20 28 39 20 28 39 20 28 39 29 37 26 76 32 74 89 37 26 76 32 74 89 66 37 26 76 32 74 89 66 More formally, a heap is a complete binary tree with the following properties: The value in the root is the smallest item in the tree. Every suberee is a heap. Inserting an Item into a Heap We use the following algorithm for inserting an item into a heap. Our approach is to place cach item initially in the bottom row of the heap and then move it up until it reaches the position where it belongs. Algorithm for Inserting in a Heap 1. Insert the new item in the next position at the bottom of the heap. 2. while new item is not at the root and new item is smaller than its parent Swap the new item with its parent, moving the new item up the heap. New items are added to the last row (level) of a heap. If a new item is larger than or equal to its parent, nothing more need be done. If we insert 89 in the heap in Figure 6.20, 89 would become the right child of 39 and we are done. However, if the new item is smaller than its parent, the new item and its parent are swapped. This is repeated up the tree until the new item is in a position where it is no longer smaller than its parent. For example, let's add 8 to the heap shown in Figure 6.21. Since 8 is smaller than 66, these values are swapped as shown in Figure 6.22. Also, 8 is smaller than 29, so these values are swapped resulting in the updated heap shown in Figure 6.23. But 8 is greater than 6, so we are done. Removing an Item from a Heap Removal from a heap is always from the top. The top item is first replaced with the last item in the heap (at the lower right-hand position) so that the heap remains a complete tree. If we used any other value, there would be a hole" in the tree where that value used to be. Then the new item at the top is moved down the heap until it is in its proper position