Max Heap: Introduction

This lesson will give a brief introduction to Max-Heaps and how their elements are inserted or removed from Max-Heaps.

We'll cover the following

Building a Max-Heap
Insertion in Max-Heap
Remove Maximum in Max-Heap

Building a Max-Heap

Max heaps follow the max heap property meaning the key at the parent node is always greater than the keys at the child 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 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}$ and 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

Max Heap: Introduction

Building a Max-Heap