Skip to main content

Guidelines

Whenever a certain element has a priority/advantage in a collection based on some property consider using a heap. Most important part of the heap is how to make decision on what to discard while iterating over a collection. Most of the time when we have the closest/minimum as desired result we want to create a maxheap, otherwise when we have farthest/maximum we want to keep minheap. The reason for this is that we want to discard the elements that suboptimal for our problem and keep only the best candidates (K Closest Points to Origin). For the instances where we have many containers/collections it's important to decide the initial set of candidates from each of the containers, the desicion on how to discard the elements and how to move to the next best element from the container we discarded the element (Smallest Range Covering Elements from K Lists). If you're using java TreeSet data structure comes in handy when dealing a situation where you need both max and min elements, you can think of it has data structure with out-of-box binary search (min, max, larger than, smaller than...).

Although not used directly with heap there are many problems related to the elements sorted by frequency which can solved either by using min/max heap or if the frequency is bounded by some upper value via bucket sort (Sort Characters By Frequency).

Another common problem is to find kth smallest or largest element in a list which can solved by keeping a heap of best k candidates and polling the element at top after iterating over the collection. A better way to do it is using Quick Select approach since it has constant space complexity and linear time complexity (in the best case). For implementation check Kth Largest Element in an Array.