# Binary heap

- tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree
- source: https://en.wikipedia.org/wiki/Binary%5Fheap

Binary tree with two additional constraints:

- Shape property: complete binary tree.
- Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order.

## Heap operations⌗

### Insert⌗

Steps to add an element to a heap:

- Add element to the bottom level of the heap at the leftmost open space.
- Compare to its parent, if they are in the correct the order, stop.
- If not, swap element with its parent and return to the previous step.

### Extract: Delete the root from heap⌗

- Replace the root of heap with the last element on the bottom level.
- Compare the new root with its children; if they are in the correct order, stop.
- If not, swap the element with one of its children and return to the previous step.

### Search⌗

### Delete⌗

### Decrease or increase key⌗

## Heap implementation with array⌗

each element *a* at index *i* has

- children at indices
*2i + 1*and*2i + 2*. - Its parent at index floor((i - 1) / 2).