Max Heap: Introduction

This lesson will give a brief introduction about Max Heap and how elements are inserted or removed from Max-Heap.

We'll cover the following

Building a Max-Heap

As mentioned in the previous lesson, a Max Heap follows the Max Heap property, which means the key at the parent node is always greater than keys at both child nodes. The following steps illustrate how we build a Max Heap:

  1. Create a new node at the end of the heap.
  2. Assign a new value to the node.
  3. Compare the value of this child node with its parent.
  4. If the value of the parent is less than that of the child, then swap them.
  5. Repeat steps 3 & 4 until the Heap property holds.

Implementing a Max-Heap

Heaps can be implemented using arrays. Initially, elements are placed in nodes in the same order as they appear in the array. Then a function is called over the whole Heap in a bottom-up manner, which “Max Heapifies” this Heap so that the Heap property is satisfied on all nodes.

When we say bottom-up we mean the function starts from the last parent node present at the n/2th position of the array, and it checks if the values at the child nodes are greater than the parent nodes. See how we constructed a Heap in the following illustration:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.