Applications of priority queues

Priority queues are an abstract collection that allow random insertion of new elements and removal of the smallest or largest element. Here are a couple of applications of priority queues:

• The A* algorithm for route finding.
• Computing the "sliding median" or "moving median average" by maintaining queues of values in the window less than or equal to and greater than or equal to the current median, respectively.

Heaps are a family of concrete data structures that can be used to implement priority queues efficiently. For implementations of heaps in F# see the article Data structures: Heaps in the F#.NET Journal.