Max Heap: Introduction

Building a max heap

As mentioned in the previous lesson, max heaps follow the max heap property, which means that the key at the parent node is always greater than the keys at the child nodes. Heaps can be implemented by using lists. Initially, elements are placed in nodes in the same order as they appear in the list. Then a function is called over the whole heap in a bottom-up manner that “Max Heapifies” or “percolates up” on this heap so that the heap property is restored. The “Max Heapify” function is bottom-up because it starts comparing and swapping parent-child key values from the last parent (at the $\frac{n}{2}$th index).

For a visual demonstration of heap creation, check out the following illustration:

Insertion in max-heap

Here is a high-level description of the algorithm to insert elements into a heap and maintain the heap property:

• Create a new child node at the end of the heap.
• Place the new key at that node.
• Compare the value with its parent node key.
• If the key is greater than the key at the parent node, then swap values.
• Repeat until you reach the root node.

For better understanding, here’s the visual representation of what was just stated:

Remove maximum in max-heap

Provided below is the algorithm that you will follow to make sure the heap property still holds after deleting the root element:

• Delete the root node.

• Move the key of the last child node at last level to root.

• Now, compare the key with its children.

• If the key is smaller than the key at any of the child nodes, swap values.

• If both keys at child nodes are greater than the parent node key, pick the larger one and see if heap property is satisfied.

• Repeat until you reach the last level.

For better understanding, here’s the visual representation of what was just stated:

---