Heap

A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap each parent node's key is greater than or equal to the keys of its children, while in a min-heap it is less than or equal. Heaps are commonly implemented as binary heaps, but variants such as d-ary heaps, binomial heaps, and Fibonacci heaps exist. The primary role of a heap is to efficiently support access to the extreme element (maximum or minimum).

Most heaps are stored in an array rather than a linked tree. For a node at index i, the left child is at 2i+1, the right child at 2i+2, and the parent at floor((i-1)/2). Insertion adds the new element at the end and repeatedly exchanges it with its parent (sift up) until the heap property holds. Removing the root replaces it with the last element and then sifts down (heapify).

Time complexities: insertion is O(log n), removal of the root is O(log n), and finding the root is O(1). Space complexity is O(n). Heaps underpin priority queues and are used in sorting (heapsort) and in graph algorithms such as Dijkstra's and Prim's algorithms, where selection of the next vertex depends on a priority measure.

Beyond data structures, the term heap also refers to the memory management region used for dynamic allocation in many programming environments. The heap is separate from the stack and is managed by a memory allocator. Allocations and deallocations can lead to fragmentation and performance considerations, and different allocators use various strategies to manage free blocks.

Variants and related structures include binary heaps, d-ary heaps, binomial heaps, Fibonacci heaps, and pairing heaps, each offering different trade-offs for insert/delete and merging operations.