Homework 9: Heaps

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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:
    [null, 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)
    [null, 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()
    [null, 93, 63, 87, 50, 61, 78, 35, 38, 40, 6, 26]