Heap

Definition

A binary tree with two conditions:

parent node’s value is bigger/smaller than its children.
every level has to be full (except last one) –> for array representation

So root is the maximum in a max heap and minimum in min heap.

Applications

Used for implementation of priority queue, heap sort, selection algorigthms (min, max, etc.), graph algorithms (Dijkstra).

Complexity

Operation	Complexity
Min/Max	$O(1)$
Insert	$O(log(n))$
Delete min/max	$O(log(n))$
BuildHeap	$O(n)$

Algorithms

Construction

Heapify

Brings the root down if it does not verify the order condition. At each level the condition is ensured by swaping with biggest element.

def heapify(H, i):
    heap_size = len(H)
    while i < heap_size:
        
        old_i = i
        l = 2*i
        r = 2*i + 1
        if l < heap_size and left_child > H[i]:
            i = left
        if r < heap_size and right child > H[i]:
            i = right
        if i == old_i:
            return
        
        swap(i, old_i)

Worst case: root brought down to last level = $O(log(n))$

Build Heap

For every node (except the leaves which already verify the heap condition) applies heapify.

def build_heap(H):
    for i in range(len(H)//2, 0, -1):
        heapify(H, i)

Example of a min-Heap building:
Build Heap

Worst case:
Heapify is O(h) with h the size of the tree and heapify is called for each internal node.
Hence we can compute the cost $c$ of heapifying $k$ nodes at a given level $i$ :

$c_i = k_i * i$

By summing we get that the worst running time is:

$0*0 + n/4 * 1 + n/8 * 2 + ... + 1 * log(n) = n$

So build_heap is $O(n)$ .

Insertion

Appends element to the end of array, and brings it up the heap by swapping it with its parent until it verifies the order condition.

Worst case: element goes up to the root = $O(log(n))$

Build Heap

Deletion

Delete the root, replace by last value and heapify the root.

Worst case: constant time for accessing last element and in the worst case the new root has to go to the bottom of the tree = $O(log(n))$

Build Heap