Heaps Exercises

   < Previous  Next >
  1. Discuss the following with your neighbor:
    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    

Last Modified: