heap

Heap

• heap is represented in an array itself. for i = (n/2 to n -1) are leaf nodes and for i = 0 to n/2-1 are nodes with atleast one children.
• For understaning, we ususally draw the binary tree. But in order to solve, we will use array only.
• For parent i : 2i+1 and 2i+2 are children nodes.
• We can call heapify algorithm on a node whose subtrees are already heapified; leaf nodes are always heapified.
• To build a max/min heap out of an array - run a loop from (n/2 -1 to 0) and call heapify on every item.
• Whenever to find top K elements in array (e.g median[means, top n/2th element], top maximum occurring elements, maximum value numbers), use a heap; We can have k numbers in the heap and decide on the max or min heap.
• K’th smallest element in an unsorted array : maintain a max heap of size K while iterating through the array. Doing this ensures that the max heap always contains the K smallest elements encountered so far. If the size of the max heap exceeds K, remove the largest element this step ensures that the heap maintains the K smallest elements encountered so far. In the end, the max heap’s top element will be the Kth smallest element. e.g https://www.geeksforgeeks.org/kth-smallest-largest-element-in-unsorted-array/