Don't understand about the HEAP

#1

I don’t understand about the use of Heap here and the way in which elements are being arranged in Heap.

#2

we are given a running stream of numbers and we can be asked a query at any time and the query is to print largest k elements so far. now one thing we can do is to have a sorted array and do insertion whenever a new number comes in a running and string and in case of query print last k elements .but this operation is costly . so we need to find a way to get k largest elements in better time complexity . Now we know that in heap we can find the maximum or minimum(based on which heap we are using ) element in O(1) time with insertion and deletion in O(logn) . So, what we are doing here is have a min-heap and fix the heap size to k .
now we can find the top element in O(1) that will be the minimum value out of k numbers inside the heap so if there is a number X , in case it is is less than top element of heap, then automatically X will be less than all the elements of the heap So, it won’t be included in the largest k elements and if it is greater than top element of heap then there is no need of top element as it won;t be included in largest k element thus we pop the top element and insert X inside the heap and we keep on doing this for every new number we encounter in the stream .

Now coming to your question that how elements are arranged inside the heap,all you have to do is imagine a tree in which root element is always less (greater) that its children in case of minHeap(maxHeap)

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.