Heaps Exercises

Priority Queues

  1. Write down the results of the following priority queue operations and then compare with your neighbor(s):
    1. Insert 42
    2. Insert 3
    3. Insert 7
    4. Top
    5. Pop
    6. Top
    7. Pop
    8. Insert 99
    9. Top
    10. Pop
    What's left in the priority queue (if anything)?

Heaps

  1. Discuss the following in a group of 3-5 people. Be prepared to share your group's conclusions.
    1. What are the advantages of using a heap data structure?
    2. Name several scenarios where a heap is advantageous.
    3. Name some scenarios where a heap is not advantageous.
  2. Are the following heaps valid? If not, do they violate the structure and/or heap-order property?
    A. Nodes with the following edges (6 is at the top): 6-5, 6-4, 5-3, 5-2, 4-1 B. Nodes with the following edges (1 is at the top): 1-2, 1-3, 2-4, 2-5, 3-6 C. Nodes with the following edges (5 is at the top): 1-4, 2-3, 2-5, 4-5
    D. Nodes with the following edges (15 is at the top): 1-5, 2-5, 3-6, 4-6, 5-7, 6-7, 7-15, 8-12, 9-12, 10-13, 11-13, 12-14, 13-14, 14-15 E. Nodes with the following edges (8 is at the top): 1-2, 2-3, 2-4, 4-6, 4-8, 5-6, 6-7, 8-12, 9-10, 10-11, 10-12, 12-14, 13-14, 14-15
  3. Insertions and Deletions
    1. Draw the resulting heap after inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an initially empty binary heap and show its array representation.
    2. Using the heap from the previous question, what does top() return?
    3. Using the heap from the previous question, draw the heap and its array after a call to pop().
    4. Using the heap from the previous question, what does top() return?
    5. Using the heap from the previous question, draw the heap and its array after a call to pop().
    6. Using the heap from the previous question, what does top() return?
    7. Using the heap from the previous question, draw the heap and its array after a call to pop().
  4. What are the following Big-Ohs for Heaps?
    Operation Average-case Worst-case
    insert    
    top    
    pop    

BuildHeap

Do the following steps individually, then confer with your neighbor(s):
  1. Write down the code for buildHeap() (feel free to use bubbleDown() or siftdown).
  2. Show the resulting heap and its corresponding array after each iteration of buildHeap() given the following initial array:
    1 2 3 4 5 6 7 8
  3. What is the Big-Oh for buildHeap() and why?

Last Modified: