Before the top elements are popped out we have preprocess the heap by building the heap and totaling that it is NlogN
At 6:00 its not klogN it is again NlogN
he meant only for extraction, it takes klogn time
k extractions and logn for each heapification
overall yes it is nlogn since we fill n elements
but in question like these u generally make a heap of only k elements and hence it becomes klogn
u do not need to push all elements just push k elements and then on the fly compare top and the upcoming element so it is klogn in that case (average) worst will ofc still be nlogn
Only making heap of k elements will not work as it will take only k elements out of n and give the first k elements. Like 5 4 2 8 4 and let say we want top 2 elements then it will return 5 and 4 but answer is 8 and 5
For this, u first make a max heap of 2 elements, now we know the element at top is the kth largest element, we traverse ahead, if the next element is smaller than current top, we pop the current top and add this new element in the heap and reheapify, so at each call it takes only logk calls, worst case is alogk, in the video he was talking about the extraction and reheapifying only after the heap is formed, only thag much part, now that is klogn
Ok, according to your algorithm if test case is 1 2 3 4 5 the we heapify 1,2 the 2 is smaller than 3 pop 2 then get 1,3 as heap in this way I end up with 1,5 as the top elements. I understood thanks.
Though last statement appears to me total absurd, but your algorithm is totally impressive if it were a minheap. Thank you
no no, u make the heap of 1,2 now if u want k largest so u make a min heap, then 1 is at top, insert 3 while popping 1, now re heapify, so 2 is at top and heap is of 2 and 3, similarly repeat the process for each element and at the end u will have 4 and 5,
similarly, for k smallest use max heap,
in the last line, suppose data is large and u have to make multiple calls, and data can be inserted and deleted at any point, in that case u store a heap and following function are performed in nlogk, he did not consider the time to create the heap, assume it is already made and then talked about the complesxity of only the extraction
not everything is an array in the real world applications