Homework 5: Heaps

  • Due before class on Monday, November 7

Remember to turn in a neat final draft of this homework on a separate sheet of paper.

  1. Write down the array that would be used to store the following heap:
  2. Draw the heap represented by the following array:
    [None, 81, 64, 70, 40, 1, 48, 10, 30]
  3. Starting with the following array-based heap, show the resulting array after performing the following series of insertions. You can show any of your work, but be sure to clearly indicate the array after each insertion.
    1
    2
    3
    
    insert(20)
    insert(60)
    insert(85)
    [None, 82, 41, 79, 39, 15, 46, 49, 38]
  4. Starting with the following array-based heap, show the resulting array after performing the following series of removals. You can show any of your work, but be sure to clearly indicate the array after each removal.
    1
    2
    3
    
    removeMax()
    removeMax()
    removeMax()
    [None, 93, 63, 87, 50, 61, 78, 35, 38, 40, 6, 26]
  5. Show the resulting array-based heap after performing a bottom-up heapify on the following list:
    [None, 31, 7, 56, 52, 98, 18, 56, 5, 40, 86, 85, 31, 83, 14, 46, 95, 20]