Homework: Priority Queues

   < Previous  Next >
Write your answers to the following questions in a flat text file hwkPriorityQueues.txt (not a Word document nor a Rich Text Format file).
So that you don't have to type heaps with ASCII characters (you're welcome), just indicate the values at each index for the underlying array. For example, for the following heap:

the answer would be written in your homework as: 
0:  A
1:  B
2:  C
3:  D
4:  E	    
5:  F 
6:  G
7:  H
8:  I
9:  J
10: K
11: L
  1. What are the two properties of a heap?
  2. Given the heap below, what would the heap look like after each of the following operations (they build on each other):
    1. pq.insert( 15 )
    2. pq.insert( 12 )
    3. pq.insert( 16 )
    4. pq.insert( 1 )
    5. pq.pop()
    6. pq.pop()
    7. pq.pop()
  3. Execute buildHeap() on the following array, showing the contents of the underlying array after each iteration (including the final iteration):
    55 77  7 44  6 66  9 88
  4. Report the following Big-Ohs for a heap insertion:
    1. Average-case
    2. Worst-case
  5. To better understand the average-case Big-Oh of a heap insertion, report the average number of swaps necessary to insert each of the following numbers into the empty node (start over again with each insertion):


    Insertion Number of Swaps
    2  
    4  
    6  
    8  
    10  
    12  
    14  
    16  
    18  
    20  
    22  
    24  
    26  
    28  
    30  
    Average  
  6. Report the following Big-Ohs for buildHeap():
    1. Average-case
    2. Worst-case
  7. To better understand the Big-Oh for buildHeap(), report the worst-case number of edges that would need to be updated for heaps with the following number of nodes:
    Number of Nodes in the Heap Total Number of Swaps for buildHeap()
    1  
    3  
    7  
    15  
    31  
    63  
    (Note: Do you see the pattern?)

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points        Question
-----------   --------------------------------------------------------------
_____ / 0.5   1
_____ / 3.5   2
_____ /   2   3
_____ / 0.5   4
_____ /   2   5
_____ / 0.5   6
_____ /   2   7

_____ /  11   Total