> For the complete documentation index, see [llms.txt](https://xavier-geerinck.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://xavier-geerinck.gitbook.io/algorithms/data-structures/trees/heap.md).

# Heap

* A heap is a binary tree where every element satisfies the heap property
* It is created to efficiently support basic priority queue operations
* In a **binary heap** the keys are stored in an array
* This heap property depends on the sort heap:

  * **Max-Heap:** parent > children (root is the biggest element)
  * **Min-Heap:** parent < children (root is the smallest element)

  ![](https://1983113773-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lc5VIoifZmhHibC2KSG%2F-Lc5VL9WESreusC3YQxb%2F-Lc5VS18eUl2rMTaTT9J%2Fheap.png?generation=1554887334620800\&alt=media)

## Reheapify - Restore Heap Order

### Bottom-Up (Swim)

* For every element in array from 0 to floor(N/2)
  * Check heap condition, swap if needed
  * If swapped, repeat swap check on the child
* Performance is O(n)

### Top-Down (Sink)

* Start from root and check children
* Swap if needed depending on the heap
* Repeat for the subheap

<https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/DemoHeapify-2x2.pdf>