When would I want to use a heap?

Question

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

Answer 1

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 N are at 2N and 2N+1. This property allows quick access-by-index. And since heaps are manipulated by swapping nodes, this allows for in-place sorting.

Answer 2

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

Answer 3

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 ant the cost of seaching 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!

Answer 4

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

Answer 5

There are plenty of good answers here, so I'll chime in with "when a pile just isn't big enough."