122

Besides the obvious answer of a Priority Queue, when would a heap be useful in my programming adventures?

Michael Myers
  • 188,989
  • 46
  • 291
  • 292
Mithrax
  • 7,603
  • 18
  • 55
  • 60

6 Answers6

148

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

However, the remainder of the array is kept partially unsorted. Thus, instant access is only possible to the largest (smallest) item. Insertions are fast, so it's a good way to deal with incoming events or data and always have access to the earliest/biggest.

Useful for priority queues, schedulers (where the earliest item is desired), etc...

A heap is a tree where a parent node's value is larger than that of any of its descendant nodes.

If you think of a heap as a binary tree stored in linear order by depth, with the root node first (then the children of that node next, then the children of those nodes next); then the children of a node at index N are at 2N+1 and 2N+2. This property allows quick access-by-index. And since heaps are manipulated by swapping nodes, this allows for in-place sorting.

Community
  • 1
  • 1
Joe Koberg
  • 25,416
  • 6
  • 48
  • 54
  • 3
    Note also it can be a convenient guaranteed NlogN sort that doesn't require additional array allocations – Overflown Apr 14 '09 at 20:53
  • why not use a stack class with an auxiliary stack to track the largest (or smallest) item. retrieval is O(1) – Ridhwaan Shakeel Mar 22 '19 at 16:14
  • @RidhwaanShakeel If you use stack your item will always be placed on head, what if the position of item needs to determined based on some property of the item like biggest event(based on number of people participated in the event). – SandeepGodara Mar 24 '19 at 19:41
82

Heaps are structures meant to allow quick access to the min or the max.

But why would you want that? You could just check every entry on add to see if it's the smallest or the biggest. This way you always have the smallest or the biggest in constant time O(1).

The answer is because heaps allow you to pull the smallest or the biggest and quickly know the NEXT smallest or biggest. That's why it's called a Priority Queue.

Real world example (not very fair world, though):

Suppose you have a hospital in which patients are attended based on their ages. The oldest are always attended first, no matter when he/she got in the queue.

You can't just keep track of the oldest one because if you pull he/she out, you don't know the next oldest one. In order to solve this hospital problem, you implement a max heap. This heap is, by definition, partially ordered. This means you cannot sort the patients by their age, but you know that the oldest ones are always in the top, so you can pull a patient out in constant time O(1) and re-balance the heap in log time O(log N).

More sophisticated example:

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

Example:

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

In the above case, 7 is the median because the array containing the smaller numbers [1, 2, 5] is of the same size of the one containing the bigger numbers [23, 27, 31]. Normally, if the array has an even number of elements, the median is the arithmetic average of the 2 elements in the middle, e.g (5 + 7)/2.

Now, how do you keep track of the median? By having 2 heaps, one min heap containing the numbers smaller than the current median and a max heap containing the numbers bigger than the current median. Now, if these heaps are always balanced, the 2 heaps will contain the same number of elements or one will have 1 element more than the other, the most.

When you add a new element to the sequence, if the number is smaller than the current median, you add it to the min heap, otherwise, you add it to the max heap. Now, if the heaps are unbalanced (one heap has more than 1 element more than the other), you pull an element from the biggest heap and add to the smallest. Now they're balanced.

Tim Richardson
  • 6,608
  • 6
  • 44
  • 71
Andre Pena
  • 56,650
  • 48
  • 196
  • 243
  • 10
    The more sophisticated example is amazing! I'm definitely gonna try this out sometime. However, I think there's a small mistake in your example. Since we need to get the median by averaging the two elements in the middle. I would assume that we need to use a min heap to store the numbers larger than the current median and a max heap to store the numbers smaller than the current median. This way we can extract the two elements in the middle in constant time and compute the median? Am I correct? – Calvin Ku Dec 02 '17 at 10:58
  • Maybe a bit more explanation is required for "you pull an element from the biggest heap and add to the smallest". I am not really sure, if you mean to remove from the bigger one and push it into the smaller one or just copy. – Sanket Ray Nov 24 '20 at 06:55
  • 1
    "Normally, if the array has an odd number of elements, the median is the arithmetic average of the 2 elements in the middle, e.g `(5 + 7)/2`." Correction, we take the average of the 2 elements in the middle, when the array has even number of elements. Thanks for this amazing answer! :) – Harshit Hiremath Nov 27 '20 at 15:20
  • Keeping track of medium is a wonderful trick! However, if you want to know medium, or any n-th number, from an array, there is an O(n) algorithm. Oops, on a second thought, putting numbers into a heap also has amortized O(n). – zyc Dec 23 '20 at 18:20
  • Loved the way you explained through the real world example. However a question looms if you know that the max is always gonna be at the top, you pop the topmost and it's still max you'll have to have it sorted right for the entire length, right? – Ashwin Phadke Dec 15 '21 at 00:25
15

The characteristic of a heap is that it is a structure that maintains data semiordered; thus, it is a good tradeoff between the cost of maintaining a complete order and the cost of searching through random chaos. That characteristic is used on many algorithms, such as selection, ordering, or classification.

Another useful characteristic of a heap is that it can be created in-place from an array!

kurumkan
  • 2,635
  • 3
  • 31
  • 55
AticusFinch
  • 2,351
  • 3
  • 25
  • 32
4

Also good for selection algorithms (finding the min or max)

Dan
  • 17,375
  • 3
  • 36
  • 39
4

anytime when you sort a temporary list, you should consider heaps.

Javier
  • 60,510
  • 8
  • 78
  • 126
1

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

QuadBiker
  • 41
  • 2