# Heaps

A binary tree has the **heap property** *iff*

- it is empty
*or* - The key in the root is larger than that in either child and both sub trees have the heap property.

A heap can be used as a priority queue: the highest priority item is at the root and is trivially extracted. But if the root is deleted, we are left with two sub-trees and we must *efficiently* re-create a single tree with the heap property.

The value of the heap structure is that we can both extract the highest priority item and insert a new one in **O(log n)** time.

Heap operations :

**Insert :**

To add an element to a heap we must perform an *up-heap* operation (also known as *bubble-up*, *percolate-up*, *sift-up*, *trickle up*, *heapify-up*, or *cascade-up*), by following this algorithm:

1. Add the element to the bottom level of the heap.

2. Compare the added element with its parent; if they are in the correct order, stop.

3. If not, swap the element with its parent and return to the previous step.

Delete :

The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called *down-heap* (also known as *bubble-down*, *percolate-down*, *sift-down*, *trickle down*, *heapify-down*, *cascade-down* and *extract-min/max*).

- Replace the root of the heap with the last element on the last 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. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)