prioritetsköer

Prioritetskøer, or priority queues, are a data structure that stores elements together with an associated priority value. In a priority queue, elements are inserted with a given priority, and the element with the highest priority (or lowest, depending on convention) is the next to be removed or returned. Typical operations include insert(item, priority), peek or top (to view the highest-priority element without removing it), and extract-min or extract-max (to remove and return the highest-priority element). Many implementations also provide decrease-key or increase-key to adjust an element’s priority after it has been inserted, and size or is-empty checks.

The most common implementation is a binary heap stored in an array. This yields O(log n) time for insert and extract-min/max, O(1) for peek, and O(n) to build a heap from an unsorted list (though a linear-time build-heap algorithm exists). Other heap variants include Fibonacci heaps and pairing heaps, which offer different trade-offs, such as improved amortized or practical performance for decrease-key, and are used in more specialized algorithms.

Variants of priority queues include min-priority queues (where the smallest priority is removed first) and max-priority queues (where the largest priority is removed first). Some implementations are designed to be stable, preserving insertion order for elements with equal priorities.

Applications of prioritetskøer are widespread: they are central to graph algorithms like Dijkstra’s shortest path and A* search, discrete-event simulation, and operating-system process scheduling. Many programming languages provide built-in priority queue structures, typically implemented as min-heaps or equivalents, suitable for a range of common tasks.