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

size

• Size should be kept track of separately

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)

Try It Out

• Insert the following elements into a min heap and a max heap
• 1, 9, 77, 14, 3, 55, 66, 7, 8

Try It Out

• Remove all elements from the following heap
• Show the state of the heap after each removal

Usage of Heaps

• Heapsort - Repeatedly remove root node
• Primm's algorithm - Finds minimum spanning tree for connected weighted undirected graphsd
• Dijkstra's algorithm - Finds single sorce shortest path between sorce vertex and every vertex in graph (used in all kinds of routing problems)
• Priority queue - Queue with different levels of priority

Heap Implementation: Array Based

• Any complete binary tree can be stored in an array
• Index 0 of the array stores the root
• Indices 1 and 2 of the array store nodes at depth 1
• Indices 3, 4, 5, and 6 of the array store nodes at depth 2
• Nodes at depth d are stored at indices 2^d - 1 ... 2^{d + 1} - 2
• Each parent node can be found at (i - 1) / 2
• Left child can be found at 2i + 1
• Right child can be found at 2i + 2

Example

• The root "49" is at index 0
• The left child of "39" is at 2(1) + 1 -> 3
• The right child of "39" is at 2(1) + 2 -> 4
• The parent of "24" is at ((5) - 1) / 2 -> 2

Try It Out

• Represent the following heap using an array