# Heap https://en.wikipedia.org/wiki/Heap_(data_structure) - Originally coined in the context of [[heapsort]], also refers to "garbage-collection storage". - (binary) Heap is a nearly perfect complete [[binary-tree]]. - Max-heap and min-heap properties. For max-heap, `A[parent(i)] >= A[i]`, i.e. the maximum is stored at the root, the same applies to subtrees. - More specifically, `A[i] >= A[2i + 1] and A[2i + 2]`. Alternatively, `parent(i) = floor((i - 1) / 2)`. - Can be used to implement a [[priority-queue]]. - A special implementation: [[fibonacci-heap]], in which `INSERT` and `DECREASE-KEY` takes only $O(1)$ time. ## Procedures - `max-heapify`: $O(\lg n)$, or $O(h)$, combine two heaps and maintain the max-heap property, by compare and exchange a node with the larger one of its two children - `build-max-heap` - $O(n)$, the tight bound is derived through summation. - Creates a heap from unsorted array. - Calling `max-heapify` from $\lfloor n/2\rfloor$ down to $1$. - [[heapsort]]: $O(n\lg n)$.