Heap

Heap Definition 

• Completebinarytree

•Partial order : for every node v, the key stored in v is greater(smaller) than or equal to its parent’s key. 

• A max tree is a tree in which the key value in each node is no smaller than the key values in its children (if any).

• A max heap is a complete binary tree that is also a max tree.

• A min tree is a tree in which the key value in each node is no larger than the key values in its children (if any).

• A min heap is a complete binary tree that isalso a min tree 

Insert into a Min Heap 

• Put into the next available leaf node

• (this is simple since it is array)

– Look at the parent of this element and swap if the parent is larger (note that the partial ordering is preserved)

– Repeat with the parent (sifting up) 

• Array representation of heap

Since the heap is a complete binary tree, we can easily locate

the parent of any element, i.e., parent(i) is at |_i/2_| 

• Analysis of insert_max_heap

The algorithm follows a path from the new leaf of the max heap to the root until it either reaches the root or reaches a position i such that the value in the parent of i is no smaller than that of i.

Since the height of the heap is log (n + 1) , O(log n) 

Delete from a Min Heap 

• Remove the root from the tree and return its value

• Remove the right most leaf and place it at the root

• Perform sifting down operations(if the key is larger than the smaller of its two children, then swap these two. Repeat this)

• Insertion / deletion : O(n) 

Application of Heap 

• Priority Queue 

• Heap Sort 

•Heap Sorting : Storing n keys in O(n), and then repetitively applying DeleteMin() operations in O(n logn). The most basic algorithm.

• Graph algorithms
– Shortest path finding algorithm
– Minimum spanning tree finding algorithm

• Scheduling algorithms 

Heap Sort 

• Ascending
– Using the Min Heap

• Descending
– Uisng the Max Heap 

Implement Heap As Array 

• Easy to use array to implement heap – array[i]’s parent is array[i/2]

– array[i]’s left child is array[2*i]
– array[i]’s right child is array[2*i+1]

• Easy to swap child and parent