Priority queue

A priority queue is an abstract data type that stores elements with priorities and retrieves an element according to priority rather than arrival order.

Binary heap: A complete binary tree in which each parent has priority no lower than its children, or vice versa. A common implementation supports efficient insertion and highest-priority removal.
Abstract data type: A specification of a data type through its values and operations, independent of implementation. Priority queues specify behavior without requiring a particular internal representation.
Dijkstra's algorithm: An algorithm that finds shortest paths from one source in a graph with nonnegative edge weights. It repeatedly extracts the unsettled vertex with the smallest tentative distance.
Binary search tree: A binary tree whose nodes are ordered so that values in each subtree fall on one side of its root. It supports ordered searches that a heap-based priority queue does not provide efficiently.
Heap property: A rule that orders each parent and child in a heap by their keys or priorities. This local ordering rule lets a priority queue expose an extreme element without sorting everything.
Ordering relation: A relation that determines how elements compare, such as less than or higher priority than. A queue needs a consistent comparison rule to decide which element comes next.
A* search algorithm: A graph-search algorithm that ranks paths using their known cost plus a heuristic estimate to the goal. Its frontier is ordered by estimated total path cost.
Fibonacci heap: A collection of heap-ordered trees with amortized constant-time insertion and decrease-key operations. It improves some theoretical operation bounds at the cost of greater implementation complexity.
Sift-up: A heap operation that moves a newly inserted element toward the root while it outranks its parent. It restores heap order after insertion into an array-based priority queue.
Comparator: A function or rule that compares two values and determines their relative order. Comparators let the same implementation support different priority conventions.

Linked from 7 pages