Binary Heaps

Max heap §

Definition §

A Binary Max Heap is a complete binary tree which has the max heap order property.

Definition - complete binary tree

A binary tree is complete if and only if

• Every level before the final level is fully filled, and
• All nodes in the final level are as far left as possible.

The max heap order property states that for every node $v$ other than the root node, the key stored at $v$ is less than or equal to the key stored at $v$’s parent.

Operations §

Insert §

• Insert the new element at the next available slot
• Ensure that the max heap order property is preserved through the bubbleUp operation.

BubbleUp §

A pseudocode definition may be given as:

bubbleUp(n):
	parent = n.parent
	if n > parent:
		swap(n, parent)
		bubbleUp(parent)

RemoveMax §

To remove the largest element:

• Swap the root element and the last element.
• Remove the last element and return it.
• Ensure that the max heap order property is preserved through the bubbleDown operation.

BubbleDown §

A pseudocode definition may be given as:

bubbleDown(n):
	a, b = n.children
	elif n < max(a, b): # less than at least one child.
		c = max(a, b)
		swap(n, c)
		bubbleDown(c)

Complexities §

Insert §

For a heap of height $h$, inserting the element into the next available slot takes constant time, and then bubbleUp is performed at most $h$ times, so the complexity is $O(\log n)$.

RemoveMax §

For a heap of height $h$, swapping and removing the largest element takes constant time, and then bubbleDown is performed at most $h$ times, so the complexity is $O(\log n)$.

Min heap §

A binary min heap is very similar to a max heap, but instead of having the max heap order property, its required min heap order property:

The min heap order property states that for every node $v$ other than the root node, the key stored at $v$ is greater than than or equal to the key stored at $v$’s parent.

Operations §

• The bubbbleUp and bubbleDown operations are copied from max heaps, with the reversal of the pairs < & >, and min and max.
• The insert operation is identical to that of max heaps
• A removeMin operation is introduced place of removeMax with identical behaviour.