Heap (Data Structure)

A heap is a complete binary tree that keeps a heap order: in a min-heap every parent is smaller than or equal to its children, so the smallest item is at the root; in a max-heap the largest item is at the root. It is usually stored compactly in an array.

Reading the top item is O(1), and inserting or removing it is O(log n). Heaps are the standard way to build a priority queue, and are used in heap sort, Dijkstra's shortest-path algorithm, task schedulers and "top K" problems. This data structure is unrelated to heap memory, the area where programs allocate objects at run time.