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

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]