Heap and priority queue

In short: A heap is a tree in which every node is smaller (min-heap) or larger (max-heap) than its children. The smallest or largest element is therefore always at the top.

In more detail: A priority queue always returns the element with the highest priority first. With a heap, insertion and removal take only O(log n). Reading the minimum costs O(1).

In Depth

• Storage: as an array: children of index i are at 2i+1 and 2i+2.
• Insert: put at the end and let it “sift up”.
• Remove: take the root, put the last element at the root, let it sink down.
• Uses: Dijkstra’s algorithm, task scheduling, event simulation, heapsort, “the k largest elements”.
• Heapsort: builds a heap and removes elements one after another: O(n log n), in place.
• Not to be confused: The heap memory (stack and heap) is something different.

See also: Tree data structure, Queue data structure