# Heap

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

&#x20;Case 1: new element >= top, ignore

&#x20;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)&#x20;

&#x20;       \= O(k + (n-k)logk)

SC: O(k)\\

```java
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&#x20;
2. Step 2: pop() k times

TC: O(n + k\*logn)

SC: O(n)

```java
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;
}
```
