Heaps

Heaps

• Tree based data structure which satisfies the heap property
• Provides good time complexity
• Partially sorted
• Not to be confused with where dynamically allocated memory is located

The heap property (invariants)

• Complete tree
• Parent and children nodes must maintain same relative ordering

Min-Heap

• Each child node must be larger than its parent
• Conversely, each parent node must be smaller than its child
• The root element always contains the minimum most element of the set

Max-Heap

• Each child node must be smaller than its parent
• Conversely, each parent node must be larger than its child
• The root element always contains the maximum most element of the set

Heap Operations

findMin/Max

• Simply look at the root node

insert

• Insert new element into next available position (so that the tree remains complete)
• To do this, insert node to the right of all nodes at depth d_max
• Or if there are already 2^d_max at this level, instead as first node at depth d_max + 1 making the tree deeper by one level
• Heapify (bubble) the element up until the heap property is correct
• For example, say we wanted to insert "49" into the following max heap

removal

• Largest/smallest value is the root of the heap
• Node is deleted and replaced with bottom most, right most node
• The remaining tree is complete but may not satisfy heap property
• Heapify down until the heap property is restored
• For example, say we wanted to remove from the following max heap

heapify

• Bubble the current node up or down in order to maintain heap property
• In insertions, continually swap with parent node until node is in correct position (possible the entire way to the root)
• In removals, continually swap with the child node until node is in correct position (possible the entire way to a leaf)
• In min heap, removals should swap with min child
• In max heap, removals should swap with max child

Operation Time Complexity

• Time complexity is related to the maximum height of the tree
• Since heaps are complete trees we get O(log n)
• Complete trees are balanced

findMin/Max	removeMin/Max	insert	heapify
O(1)	O(log n)	O(log n)	O(log n)

Usage of Heaps

heapsort, primms, dykstra, priority queue

Heap Implementation: Array Based