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. The differences between priority queues and heaps
    2. What are the advantages of using a heap data structure?
    3. Name several scenarios where a heap is advantageous.
    4. 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().

BuildHeap

  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 O for buildHeap() and why?

Algorithm Efficiency

  • What are the following Big Os for Heaps?
    Operation Average-case Worst-case Notes
    insert      
    top      
    pop      
    buildHeap      

    • Last Modified: