Heaps

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap every node's key is greater than or equal to its children's keys, and in a min-heap every node's key is less than or equal to its children's keys. Heaps are typically nearly complete binary trees, allowing efficient array-based storage and predictable performance characteristics.

Binary heaps are the most common type. They are stored in an array, with the left child of index i at 2i+1, the right child at 2i+2, and the parent at floor((i-1)/2). Insertion adds an element at the end and sifts it up to restore the heap property; extraction removes the root and sifts the last element down. Peeking at the root is O(1).

Other heap variants, such as binomial heaps, Fibonacci heaps, pairing heaps, and d-ary heaps, emphasize faster merges or decrease-key operations. Binary heaps support insert and extract-min/max in O(log n) time, while more advanced designs offer better amortized bounds for certain operations, particularly decrease-key and merge.

Applications include priority queues and sorting. Heapsort uses a heap to produce a sorted sequence in O(n log n) time. Heaps are also used in algorithms such as graph traversals and scheduling systems where efficient retrieval of the minimum or maximum element is required.