Heap

Kth Largest Element in Unsorted Array - Heapify vs insert

-> sorting: nlog(n) & o(1) space
-> Max heap: maximum value on top
- create a max heap by heapifying - O(n)
- No need to do one by one insert as it will take n.log(n)
- pop for k times - k.log(N)
- Total : N + k.log(N)
-> Min heap: min value on top
- create a min heap of size k
- first push k elements (one by one) => k.log(k)
- then after for remaining n-k -> pop and then push => (n-k).log(k)
- total (Essentially we push every element in heap) - n.log(k)

Comparison of Approaches

1. Sorting Approach
   • Sort the array and pick the Kth largest element.
   • Time Complexity: O(Nlog⁡N)
   • Space Complexity: O(1) if sorting is done in place.
2. Min Heap Approach
   • Use a min heap (priority queue) of size K.
   • Iterate through the array, maintaining only the top K largest elements.
   • The root of the min heap will be the Kth largest element.
   • Time Complexity: O(Nlog⁡K)
     • Building the heap takes O(Klog⁡K)
     • Inserting N−K elements and maintaining heap property takes O((N−K)log⁡K)
   • Space Complexity: O(K) (since we store only K elements)

Conclusion

• For large N and small K → Min heap is better.
• For small N or if K is close to N → Sorting is fine.
• If modifications to the array are not allowed → Min heap is useful.