Min Heap: An Introduction

This lesson will give a brief introduction about Min Heap, and how elements are inserted or removed from them.

Building a Min-Heap

A Min Heap follows the Min Heap property, which means the key at the parent node is always smaller than keys at both children nodes.

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 “Min 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 in the n/2th position of the array, and checks if the values at the children nodes are smaller than the parent node. If yes, then swap the values; if no, then move to the next parent node. See how we constructed a Heap in the following illustration:

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