Min Heap: Introduction

A brief introduction to min heaps and how elements are inserted and removed from them.

We'll cover the following

- Building a min heap
- Insertion in min heap
- Remove minimum in min heap

Building a min heap

Building a mMin hHeap # As mentioned in a previous lesson, min heaps follow the min heap property, which means that the key at the parent node is always smaller than the keys at the child nodes. Heaps can be implemented using vectors. Initially, elements are placed in nodes in the same order as they appear in the vector. Then, a function is called over the whole heap in a bottom-up manner that “Min Heapifies” or “percolates up” on this heap so that the heap property is restored. The “Min 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:

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

Introduction to Complexity Measures

Introduction to Arrays

Introduction to Linked Lists

Introduction to Stack/Queues

Introduction to Graphs

Introduction to Trees

Trie

Introduction to Heap

Introduction to Hashing

Summary of Data Structures

Min Heap: Introduction

Building a min heap