PriorityQueue Aside: Selection Problem

Consider the following programming challenge:

You are given an array of $n$ integers in no particular order. Write a program that prints out the $k^{\text{th}}$ best (max or min) value where $k \le n$.

Students came up with the following strategies to solve this problem (assuming "best" means "max"):

Strategy 1: Heapify the array using Floyd's algorithm to build a max-heap. Then, perform $k$ remove.

Strategy 2: Heapify the first $k$ element using Floyd's algorithm to build a min-heap. Then, for the remaining $n-k$ elements, compare each to best (min) in the heap; if the element is larger, remove the best (min) and insert the (larger) element instead. When done, the best element in the min-hep is the $k^{\text{th}}$ best value in the collection!

Exercise For each strategy, perform asymptotic analysis for it time complexity.

Solution

Strategy 1:

  • $O(n)$ heapify using Floyd's algorithm
  • $k \times O(\lg n)$ remove.
  • Total: $O(n + k\lg n)$

Strategy 2:

  • $O(k)$ heapify the first $k$ elements using Floyd's algorithm
  • for the other $n-k$ elements:
    • compare each to best (min) in heap: $O(1)$
    • if it is larger,
      • remove the best (min): $O(\lg k)$
      • insert the larger element instead: $O(\lg k)$
  • Total: $O(k) + (n-k) \times O(\lg k) \in O(k + n \lg k)$