Applications of Priority Queues - the Selection Problem

1. The problem

Given a list of N elements (here "list" means a sequence, it does not mean ADT list)
and an integer k, k £ N, find the k^th largest element.

2. Solution 1

Sort the elements in an array and return the element in the k^th position.

Complexity:


simple sorting algorithm O(N²)
advanced sorting algorithm O(NlogN)
3. Solution 2

Read k elements in an array and sort them. Let S_k be the smallest element. For each next element E do the following:


If E > S_k remove S_k and insert E in the appropriate position in the array
Return S_k

Complexity: O(N*k)


k² for the initial sorting of k elements
(N-k)*k for inserting each next element
O(k²)+ O((N-k)*k) = O(k² + N*k - k²) = O(N*k)

Worst case: k = N/2, complexity: O(N²)

4. Solution 3

Assume we change the heap-order property - the highest priority corresponds to the highest key value.

Read N elements in an array
Build a heap of these N elements - O(N)
Perform k DeleteMax operations - O(klogN)

Complexity: O(N) + O(klogN)
For k = N/2 the complexity is O(NlogN)

5. Solution 4

We return back to the usual heap-order property – the smallest element is at the top.

Build a heap of k elements. The k-th largest element among k elements is the smallest element in that heap and it will be at the top. Complexity O(k)

Compare each next element with the top element O(1)
If the new element is larger, DeleteMin the top element and insert the new element in the heap. - O(log(k))

At the end of the input the smallest element in the heap is the k-th largest element in the list of N elements.

Complexity: O(k) + O((N-k)*log(k)) = O(Nlog(k))