Heap

overview

Summary

A heap is a complete_binary_tree that satisfies the heap_property. In a min_heap the parent is ≤ children; in a max_heap the parent is ≥ children. Commonly stored in an array_representation for O(1) peek. Typical operations: insert and extract_min/extract_max run in O(log n). heapify/build_heap from an array is O(n). Heaps power a priority_queue. With 0-based arrays: parent of i is (i-1)/2; children are 2i+1 and 2i+2.