Similar Questions : Kth Element

If a question requires finding the Kth largest or smallest item, it is likely that heaps will be involved. Variations of words like "smallest" and "largest" may appear, such as:

We start with K elements and remove the least largest item in favor of greater ones. To remove the smallest item, we need a min heap.

We start with K elements and assume the smallest K item. Then, we remove the most largest item in favor of smaller ones. To remove the largest item, we need a max heap.

The Kth <superlative> are not always simple. In some questions we cannot add values directly to the heap. Instead, we calculate a value to determine their order, such as distance from a particular point or frequency for items, and use that value to sort them. We can then return the corresponding Kth element. These questions will have the following features, which are telltale signs that we are supposed to use a heap, we will talk about these questions in the next module. Heaps with a payload

A heap is also useful when dealing with a stream of data that requires finding the minimum and maximum items. The heap maintains partial sortedness while returning the top items, which saves time by not needing to sort the entire array, making it a good choice when items are constantly leaving and coming in.

Examples: If new data is constantly arriving or old data is leaving and we only need to return the maximum or minimum values, consider using heaps for the following scenarios:

A queue for running tasks. The topmost task is processed and removed from the queue once completed, while simultaneously adding more tasks to it.
Sales are conducted throughout the day, and the top three sales are always available.
Customers with the highest points are given priority rewards ahead of everyone else. After redeeming their reward, their priority is lowered, and they are added back to the queue with a lower priority.