Table of Contents
min heap vs max heap
MaxHeap is good for keeping track of the k smallest items
MinHeap is good for keeping track of the k largest items
Why?
Because the root of a heap is the most accessible one and can be easily popped off. So for example a MinHeap always keeping track of the current smallest one, if an incoming one is smaller, we ignore it, if bigger, we pop off the root, and add it to the heap. This keeps the heap to contain the k largest ones. And vice vesa for MaxHeap.
If we do it the other way around. For example use MaxHeap to keep track of the k largest items. We can't keep only the k items. We need to first insert all items into the heap, then pop k times to get to the result, less efficient.
haochen xu