Consider the (partial) class PriorityQueue below. public class PriorityQueue { } private T[] item; private int...

 

Transcribed Image Text:

Consider the (partial) class PriorityQueue below. public class PriorityQueue<T> { } private T[] item; private int numItems; public void PercolateUp (int i) { public T DeleteLowest () { ... } } Suppose that PriorityQueue is implemented as a binary heap where the root (the item with the highest priority) is stored at item [1]. a) (2 marks) The method Delete Lowest removes and returns the item with the lowest priority from the binary heap. Comment on which items in the binary heap are candidates for lowest priority. b) (10 marks) Complete the body of the method Delete Lowest. Suppose that type T has implemented the IComparable interface where CompareTo (T element) returns +1 if the current item has a higher priority than element; 0 if the current item has the same priority as element; and -1 if the current item has a lower priority than element. Note that although Delete Lowest may use PercolateUp, it is not necessary to implement the method PercolateUp itself. c) (2 marks) Using the "Big-Oh" notation, state the worst case time complexity of DeleteLowest in terms of the number of items (n) in the priority queue. Consider the (partial) class PriorityQueue below. public class PriorityQueue<T> { } private T[] item; private int numItems; public void PercolateUp (int i) { public T DeleteLowest () { ... } } Suppose that PriorityQueue is implemented as a binary heap where the root (the item with the highest priority) is stored at item [1]. a) (2 marks) The method Delete Lowest removes and returns the item with the lowest priority from the binary heap. Comment on which items in the binary heap are candidates for lowest priority. b) (10 marks) Complete the body of the method Delete Lowest. Suppose that type T has implemented the IComparable interface where CompareTo (T element) returns +1 if the current item has a higher priority than element; 0 if the current item has the same priority as element; and -1 if the current item has a lower priority than element. Note that although Delete Lowest may use PercolateUp, it is not necessary to implement the method PercolateUp itself. c) (2 marks) Using the "Big-Oh" notation, state the worst case time complexity of DeleteLowest in terms of the number of items (n) in the priority queue.

Answer rating: 100% (QA)

a The items that are candidates for lowest priority are the leaves of ... View the full answer