Heap

2.3 Kth smallest in unsorted array

Assumption: array size = n

Summary: It is hard to say either minHeap or maxHeap is better in solving this problem, considering whether k is << n or ~~ n. In terms of TC, it is debatable. In terms of SC, maxHeap is better. O(k) vs. O(n)

Corner case: k == 0

Input: int[] array, int k

Output: int[] k smallest numbers

Solution 1: maxHeap

1. Step 1: Heapify the first k elements to form a max heap of size k

2. Step 2: Iterate over the remaining n - k elements, compare them to the largest of the previous k candidates

Case 1: new element >= top, ignore

Case 2: new element < top, update top → new element

TC: heapify k elements: O(k) + call k elements: O(klogk) + iterate remaining: O((n-k)*logk)

= O(k + (n-k)logk)

SC: O(k)

public int[] kSmallest(int[] array, int k) {
   if (array.length == 0 || k == 0) {
     return new int[0];
   };
   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
     @Override
     public int compare(Integer f1, Integer f2) {
       if (f1.equals(f2)) {
         return 0;
       }
       return f1 > f2 ? -1 : 1;
     }
   });
 
   for (int i = 0; i < array.length; i++) {
     if (i < k) {
       maxHeap.offer(array[i]);
     } else if (array[i] < maxHeap.peek()) {
       maxHeap.poll();
       maxHeap.offer(array[i]);
     }
   }
   int[] res = new int[k];
   for (int i = k - 1; i >= 0; i--) {
     res[i] = maxHeap.poll();
   }
   return res;
 }

Solution 2: minHeap:

1. Step 1: heapify all elements

2. Step 2: pop() k times

TC: O(n + k*logn)

SC: O(n)

public int[] kSmallest(int[] array, int k) {
	int[] res = new int[k];
	if (k == 0) {
		return res;
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < array.length; i++( {
	pq.offer(array[i]);
}
for (int i = 0; i < k; i++) {
	res[i] = pq.poll();
}
return res;
}