Home/Blog/Programming/Data Structures 101: How to build min and max heaps

Data Structures 101: How to build min and max heaps

8 min read

May 29, 2024

content

What is a Heap?Pros and cons of Heaps Applications of Heap Data Structure Essential Operations in Heaps How to build a max Heap Implementing Max Heap in JavaScript How to build a min Heap Implementing Min Heap in JavaScript Heaps Challenge: Convert Max Heap to Min Heap What to learn next Continue reading about JavaScript and data structures

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Data structures are important in computer programming for organizing, managing, and storing data in a quick and efficient manner. Data structures are an absolutely essential skill for any developer to have in their toolkit.

Today we will be continuing with the Data Structures 101 series, focusing on Heaps, a special tree-based data structure that implements a complete binary tree.

Today, we will cover:

What is a Heap?
Essential Operations in Heaps
How to build a Max Heap
How to build a Min Heap
Heaps challenge: hands-on practice
What to learn next

Get hands-on with data structures today

Data Structures for Coding Interviews in JavaScript

Data structures are amongst the very fundamentals of Computer Science and are often a core decision in developing efficient programs. Consequently, they are also largely categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This course contains a detailed review of all the common data structures and provides implementation level details in JavaScript to allow readers to become well equipped with all the different data structures they can leverage to write better code!

35hrs

Beginner

65 Challenges

24 Quizzes

Heaps use complete binary trees to avoid holes in the array. A complete binary tree is a tree where each node has at most two children and the nodes at all levels are full, except for the leaf nodes which can be empty. Heaps are built based on the heap property, which compares the parent node key with its child node keys.

In a later part of this article, we would discuss in detail Min Heap built on Min Heap property and Max Heap built on Max Heap property.

It is important to note that heaps are not always sorted, the key condition that they follow is that the largest or smallest element is placed on the root node (top) depending if it is a Max or Min Heap. The Heap data structure is not the same as heap memory.

Pros and cons of Heaps#

Applications of Heap Data Structure#

Heaps are efficient for finding the min or max element in an array and are useful in order statistics and selection algorithms. The time complexity of getting the minimum/maximum value from a heap is $O(1)$ , (constant time complexity).

Priority queues are designed based on heap structures. It takes $O(log(n))$ time to insert (insert()) and delete (delete()) each element in the priority queue efficiently.

Heap-implemented priority queues are used in popular algorithms like:

Prim’s algorithm
Dijkstra’s algorithm
Heapsort algorithm

Essential Operations in Heaps#

The following are the essential operations you might use when implementing a heap data structure:

heapify: rearranges the elements in the heap to maintain the heap property.
insert: adds an item to a heap while maintaining its heap property.
delete: removes an item in a heap.
extract: returns the value of an item and then deletes it from the heap.
isEmpty: boolean, returns true if boolean is empty and false if it has a node.
size: returns the size of the heap.
getMax(): returns the maximum value in a heap

How to build a max Heap#

Elements in a max heap follow the max heap property. This means that the key at the parent node is always greater than the key at both child nodes. To build a max heap, you:

Create a new node at the beginning (root) of the heap.
Assign it a value.
Compare the value of the child node with the parent node.
Swap nodes if the value of the parent is less than that of either child (to the left or right).
Repeat until the largest element is at the root parent nodes (then you can say that the heap property holds).

These steps can also be followed when inserting new elements into a heap. The key here is, whatever operation being carried out on a Max Heap, the heap property must be maintained.

To remove/delete a root node in a Max Heap, you:

Delete the root node.
Move the last child node of the last level to root.
Compare the parent node with its children.
If the value of the parent is less than child nodes, swap them, and repeat until the heap property is satisfied.

Let’s take a look at what this looks like in code. In the next section, we will implement a max heap using JavaScript.

Implementing Max Heap in JavaScript#

Before we get into building a Max Heap, take a look at some of the methods we’ll implement and what they do:

_percolateUp(): restores the heap property from a child node to a root node.
_maxHeapify(): restores the heap property from a specific node down to leaf nodes.
insert(): appends a given value to the heap array and rearranges elements based on their heap property. On every new insert, the heap grows uniformly, and the size increases by one.
getMax(): returns the maximum value in the heap (root node) without modifying the heap. Note that the time complexity here is constant time $O(1)$
removeMax(): returns and removes the maximum value in the heap (think of pop()). The time complexity of this function is in $O(log(n))$ .

If the heap size is greater than one, it stores the maximum value to a variable, swaps that value with the last leaf, and deletes the maximum value from the heap.

If the heap has just one element, it deletes and returns the value of that element, the last condition is if the heap is empty, it returns null.

The __percolateUp() method is called recursively on each parent node until the root is reached. For every node to be positioned following the max-heap property, we call the __maxHeapify() method at every index of that array, starting from the bottom of the heap.

class maxHeap {
    constructor() {
        this.heap = [];
        this.elements = 0;
    };
    insert(val) {
        if (this.elements >= this.heap.length) {
            this.elements = this.elements + 1;
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };
    getMax() {
        if (this.elements !== 0)
            return this.heap[0];
        return null;
    };
    removeMax() {
        let max = this.heap[0];
        if (this.elements > 1) {
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__maxHeapify(0);
            return max
        } else if (this.elements === 1) {
            this.elements = this.elements - 1;
            return max;
        } else {
            return null;
        }
    };
    __percolateUp(index) {
        const parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] < this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };
    
    __maxHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let largest = index;
        if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
            largest = left
        }
        else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
            largest = right
        else if (largest !== index) {
            const tmp = this.heap[largest];
            this.heap[largest] = this.heap[index];
            this.heap[index] = tmp;
            this.__maxHeapify(largest);
        }
    };
    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__maxHeapify(i);
        }
    };
};
let heap = new maxHeap();

Get hands-on with data structures today

Data Structures for Coding Interviews in JavaScript

35hrs

Beginner

65 Challenges

24 Quizzes

How to build a min Heap#

Intuitively, we can say that elements in a min heap follow the min heap property, as this is opposite to max heaps. The key at the parent node is always less than the key at both child nodes. To build a min heap we:

Create a new child node at the end of the heap (last level).
Add the new key to that node (append it to the array).
Move the child up until you reach the root node and the heap property is satisfied.

To remove/delete a root node in a min heap:

Delete the root node.
Move the key of the last child to root.
Compare the parent node with its children.
If the value of the parent is greater than child nodes, swap them, and repeat until the heap property is satisfied.

Implementing Min Heap in JavaScript#

Before we get into building a min heap, note that its implementation is similar to that of Max Heap. minHeapify() restores the heap property. getMin() returns the minimum value in the heap (root node) without modifying the heap. And removeMin() deletes the minimum value and returns it.

class minHeap {
    constructor() {
        this.heap = []
        this.elements = 0;
    };
    insert(val) {
        if (this.elements >== this.heap.length) {
            this.elements = this.elements + 1
            this.heap.push(val);
            this.__percolateUp(this.heap.length - 1);
        }
        else {
            this.heap[this.elements] = val;
            this.elements = this.elements + 1;
            this.__percolateUp(this.elements - 1);
        }
    };
    
    getMin() {
        if (this.heap.length !== 0)
            return this.heap[0];
        return null;
    }
    removeMin() {
        const min = this.heap[0];
        if (this.elements > 1) {            
            this.heap[0] = this.heap[this.elements - 1];
            this.elements = this.elements - 1;
            this.__minHeapify(0);
            return min;
        } else if (this.elements == 1) {
            this.elements = this.elements - 1;
            return min;
        } else {
            return null;
        }
    };
    __percolateUp(index) {
        let parent = Math.floor((index - 1) / 2);
        if (index <= 0)
            return
        else if (this.heap[parent] > this.heap[index]) {
            let tmp = this.heap[parent];
            this.heap[parent] = this.heap[index];
            this.heap[index] = tmp;
            this.__percolateUp(parent);
        }
    };
    __minHeapify(index) {
        let left = (index * 2) + 1;
        let right = (index * 2) + 2;
        let smallest = index;
        if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
            smallest = left;
        }
        if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
            smallest = right;
        if (smallest !== index) {
            let tmp = this.heap[smallest];
            this.heap[smallest] = this.heap[index];
            this.heap[index] = tmp;
            this.__minHeapify(smallest);
        }
    }
    buildHeap(arr) {
        this.heap = arr;
        this.elements = this.heap.length;
        for (let i = this.heap.length - 1; i >= 0; i--) {
            this.__minHeapify(i)
        }
    }
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //you should get -10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //builds this new heap with elements from the array
console.log(newheap.getMin()) //this logs 3
newheap.removeMin();
console.log(newheap.getMin())

Heaps Challenge: Convert Max Heap to Min Heap#

Let’s take our learning one step further with a hands-on challenge. Our goal here is to convert a max heap to a min heap. Follow along with our code solution to see how it’s done.

Problem Statement: Implement a function convertMax(maxHeap) which will convert a binary max heap into a binary min heap where maxHeap is an array in the maxHeap format (i.e. the parent is greater than its children). Your output should be a converted array.

Sample Input:

maxHeap = [9,4,7,1,-2,6,5]

Sample Output:

result = [-2,1,5,9,4,6,7]

function minHeapify(heap, index) {
    var left = index * 2;
    var right = (index * 2) + 1;
    var smallest = index;
    if ((heap.length > left) && (heap[smallest] > heap[left])) {
        smallest = left
    }
    if ((heap.length > right) && (heap[smallest] > heap[right]))
        smallest = right
    if (smallest != index) {
        var tmp = heap[smallest]
        heap[smallest] = heap[index]
        heap[index] = tmp
        minHeapify(heap, smallest)
    }
    return heap;
}
function convertMax(maxHeap) {
    for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
        maxHeap = minHeapify(maxHeap, i)
    return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))

What to learn next#

Congratulations on making it to the end of this article. I hope you now have a good knowledge of how heaps work and can confidently build a heap with Javascript.

Here are some common challenges that would help test your knowledge of heap data structure. You can expect to see these questions in a coding interview:

Convert Max Heap to Min Heap
Find k smallest element in an array
Find k largest element in an array
Check if a given array represents min heap or not
Merge M sorted lists of variable length
Find smallest range with at-least one element from each of the given lists

To find answers to these questions and continue your learning, check out Educative’s course Data Structures for Coding Interviews in JavaScript. It will give you a detailed explanation of all common JavaScript data structures with solutions to real-world data structure problems. You’ll become well equipped with all the different data structures they you leverage to write better code.

Happy learning!

Continue reading about JavaScript and data structures#

Frequently Asked Questions

What is the difference between min and max heap?

Developers use the min heap to collect the minimum component of a given heap. In contrast, developers use the max heap to collect the maximum component of the heap.

What are heaps in data structure?

A heap is a tree-based data structure where all the nodes follow a specific order. For example, if one node is the parent of another, the value of the parent node maintains a certain order relative to the value of the child node. This order is consistently followed throughout the entire tree.

Written By:

Jerry Ejonavi

Join 2.5 million developers at

Explore the catalog

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments