When do I want to use a bunch?

Question

Besides the obvious priority queue answer, when would a bunch be useful on my programming adventures?

Answer 1

Use it when you need quick access to the largest (or smallest) element, because this element will always be the first element in the array or in the root of the tree.

However, the rest of the array is kept partially unsorted. Thus, instant access is only possible for the largest (smallest) item. The inserts are quick, so this is a good way to handle incoming events or data and always have access to the earliest / largest.

Useful for priority queues, schedulers (where the earliest element is required), etc.

A heap is a tree where the parent value of a node is greater than any of its descendants.

If you think of the heap as a binary tree stored linearly in depth, first with the root of the node (then descendants of this node, then descendants of these nodes); then the children of a node with index N are 2N + 1 and 2N + 2. This property allows you to quickly access the index. And since heaps are managed using exchange nodes, this allows sorting by location.

Answer 2

Heaps are structures designed for quick access to min or max .

But why do you need this? You can simply check each entry in the add to see if it is the smallest or the largest. Thus, you always have the smallest or largest constant time O(1) .

The answer is that heaps allow you to pull out the smallest or largest and quickly find out NEXT the smallest or largest . That is why he called the priority order.

Real world example (not very fair world):

Suppose you have a hospital in which patients are visited according to age. The oldest are always in the first place, regardless of when he / she got in line.

You cannot just keep track of the oldest, because if you pull it out, you do not know the next oldest. To solve this hospital problem, you implement the maximum heap . This heap, by definition, is partially streamlined. This means that you cannot sort patients by their age, but you know that the oldest of them are always at the top, so you can pull the patient out at constant O(1) and rebalance the heap during O(log N) .

More complex example:

Suppose you have a sequence of integers and you want to track median . Median is a number that is in the middle of an ordered array.

Example:

 [1, 2, 5, 7, 23, 27, 31] 

In the above case, 7 is median because the array containing the smaller numbers [1, 2, 5] has the same size as the larger numbers [23, 27, 31] . Usually, if the array has an even number of elements, the median is the arithmetic mean of two elements in the middle, for example (5 + 7)/2 .

Now, how do you track the median? Having 2 heaps , one minute heap containing numbers smaller than the current median, and a maximum heap containing numbers larger than the current median. Now, if these heaps are always balanced, 2 heaps will contain the same number of elements, or one will have 1 element more than the other.

When you add a new element to the sequence, if the number is less than the current median, you add it to the heap of minutes, otherwise you add it to the maximum heap. Now, if the heaps are not balanced (one heap has more than 1 element more than the other), you pull the element from the largest heap and add to the smallest one. Now they are balanced.

Answer 3

The characteristic of the heap is that it is a structure that stores data in semi-ordered data; thus, this is a good compromise between the cost of maintaining the full order ant cost of passing through random chaos. This characteristic is used for many algorithms, such as selection, ordering, or classification.

Another useful feature of the heap is that it can be created in place from an array!

Answer 4

Also useful for selection algorithms (min or max search)

Answer 5

Anytime you sort a temporary list, you must consider heaps.

Answer 6

You can use minHeap or maxHeap if you want to access the smallest and largest elements, respectively.