saiyan
January 15th, 2007, 06:06 PM
Hey Guys... I need help quick.
This came on a past paper... and I need tips on how to approach it..
Thanks in advance.
Saiyan.
These are the time complexities (in the worst case) of different implementations of a priority queue.
SortedArray, UnsortedArray, Heap
Adding an element: O(n), O(1), O(log n)
Removing the max O(1), O(n), O(log n)
Test if empty O(1), O(1), O(1)
An application needs to add and retrieve k elements from a priority queue.
What is the the overall complexity for this when implemented with an unsorted array, or a sorted array, or a heap ? Which implementation has the best overall complexity ? (40%)
This came on a past paper... and I need tips on how to approach it..
Thanks in advance.
Saiyan.
These are the time complexities (in the worst case) of different implementations of a priority queue.
SortedArray, UnsortedArray, Heap
Adding an element: O(n), O(1), O(log n)
Removing the max O(1), O(n), O(log n)
Test if empty O(1), O(1), O(1)
An application needs to add and retrieve k elements from a priority queue.
What is the the overall complexity for this when implemented with an unsorted array, or a sorted array, or a heap ? Which implementation has the best overall complexity ? (40%)