Heap - 5: Find Kth Smallest Value in given array

preview_player
Показать описание
Solution - 1: using Max heap
- Crate max heap of k size
- Now keep adding other element
- If current value is greater than peek value, then we need not do anything
- If current value is smaller than peek value, we poll top value & insert current value
- At last after iteration of all value, the peek of maxHeap will be kth smallest

Solution - 2: using Min heap
- Create min heap & insert all value into it
- Now poll k - 1 values from it
- Now the peek value at the moment will be kth smallest value
Do Watch video for more info

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★
Рекомендации по теме
Комментарии
Автор

2:53 How can you make a min heap in O(N) time?
Creating the min heap will require continuous insertion and call to heapify. And then pulling k elements out will take klog(N)

duedares
Автор

If k elements insertion timecomplexity is klogk then n elements insertion would be nlogn ?

rachelross