Introduction to Min-Heap - Naukri Code 360

Introduction

Min heaps are a special kind of data structure that prioritize the smallest elements, putting them at the forefront. This setup is incredibly useful for tasks that need quick access to the smallest item, like in certain sorting algorithms or when managing priority queues. In short a min heap makes sure that the smallest number is always easy to find and access, streamlining processes that rely on this kind of organization.

In this article, we'll cover everything you need to know about min heaps: from their purpose and various use cases with examples We'll also distinguish min heaps from max heaps to clarify their unique roles, look into how min heaps are constructed internally, and explore the range of operations you can perform with them.

Purpose & Use Cases of Min-Heap

Min heaps aren't just a random concept; they have some pretty cool uses in computer science. The main job of a min heap is to keep the smallest number at the top, making it super quick to access. This comes in handy for a lot of tasks. For example, when managing tasks in a computer program, you might want to deal with the most urgent ones first. Min heaps help with that by keeping the smallest (or most urgent) tasks easy to reach.

They're also great for algorithms that need to frequently find and use the smallest number. Imagine you're sorting a bunch of numbers; min heaps can help organize them efficiently. Or, if you're working on a network problem where you need to find the shortest path, min heaps can be a lifesaver.

Min Heap in C++

When you're working with min heaps in C++, you often use a priority queue from the Standard Template Library (STL). It's like a special box that can automatically sort things for you, keeping the smallest item ready to grab.

Here's a simple way to set up a min heap in C++:

C++

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // This is how you make a min heap in C++
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // Let's add some numbers to the heap
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(15);

    // Now, let's take a look at the smallest number
    std::cout << "The smallest number in the heap is: " << minHeap.top() << std::endl;

    // And we'll remove it from the heap
    minHeap.pop();

    // Let's check the smallest number again
    std::cout << "Now, the smallest number is: " << minHeap.top() << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The smallest number in the heap is: 5
Now, the smallest number is: 10

In this code, we create a min heap using a priority queue. We add some numbers to it and then peek at the smallest number. After removing the smallest number, we check again to see which number is now the smallest. It's a straightforward way to manage your data, keeping everything tidy and accessible.

Min Heap in Java

In Java, creating a min heap involves using the PriorityQueue class, which is part of the Java Collections Framework. It's like a special kind of queue that knows how to sort its elements, always keeping the smallest one at the front.

Java

Java

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        // Creating a min heap in Java
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Adding some numbers to the heap
        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(15);

        // Peek at the smallest number in the heap
        System.out.println("The smallest number in the heap is: " + minHeap.peek());

        // Remove the smallest number
        minHeap.poll();

        // Peek again to see the new smallest number
        System.out.println("Now, the smallest number is: " + minHeap.peek());
    }
}

You can also try this code with Online Java Compiler

Run Code

Here's a simple example of how to use a PriorityQueue to create a min heap in Java:

Output

The smallest number in the heap is: 5
Now, the smallest number is: 10

In this Java code, we create a PriorityQueue to serve as our min heap. We add a few numbers and then use peek() to look at the smallest number without removing it. After calling poll(), which removes the smallest number, we peek again to find the new smallest number. This way, we can efficiently manage a set of numbers, always keeping them in order.

Min Heap in C#

Creating a min heap in C# is a bit different from Java and C++ because C# doesn't have a built-in min heap structure. However, we can use the SortedSet class from the System.Collections.Generic namespace as a close alternative. It sorts its elements automatically, but it's worth noting that it doesn't allow duplicate values.

Here's a basic example of how you might simulate a min heap in C# using SortedSet:

C#

using System;
using System.Collections.Generic;

public class MinHeapExample {
    public static void Main() {
        // Simulating a min heap using SortedSet in C#
        SortedSet<int> minHeap = new SortedSet<int>();

        // Adding some elements to the heap
        minHeap.Add(10);
        minHeap.Add(5);
        minHeap.Add(15);

        // Checking the smallest element
        Console.WriteLine("The smallest number in the heap is: " + minHeap.Min);

        // Removing the smallest element
        minHeap.Remove(minHeap.Min);

        // Checking the smallest element again
        Console.WriteLine("Now, the smallest number is: " + minHeap.Min);
    }
}

Output

The smallest number in the heap is: 5
Now, the smallest number is: 10

In this code, we use SortedSet to add numbers and automatically keep them sorted. The Min property gives us the smallest number, similar to how we'd peek at the top of a min heap. When we want to remove the smallest number, we use Remove() with the smallest element as the argument. This approach isn't a perfect min heap because of the no-duplicates rule, but it's a handy way to manage sorted data in C#.

Min Heap in Python

Python makes working with min heaps pretty straightforward, thanks to the heapq module. This module provides an easy way to transform a regular list into a min heap, where the smallest element is always at position 0.

Here's how you can use heapq to create and manage a min heap in Python:

Python

Python

import heapq

# Creating an empty min heap
min_heap = []

# Adding some numbers to the heap
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 15)

# Let's see the smallest number in the heap
print(f"The smallest number in the heap is: {min_heap[0]}")

# Removing the smallest number
heapq.heappop(min_heap)

# Checking the smallest number again
print(f"Now, the smallest number is: {min_heap[0]}")

You can also try this code with Online Python Compiler

Run Code

Output

The smallest number in the heap is: 5
Now, the smallest number is: 10

In this example, we start with an empty list and use heappush to add numbers, turning the list into a min heap. The heappop function removes and returns the smallest number, keeping the heap structure intact. Python's heapq is efficient and simple, making it a great choice for implementing min heaps without much hassle.

Difference between Max Heap and Min Heap

Feature	Max Heap	Min Heap
Top Element	Largest number is at the top.	Smallest number is at the top.
Ordering	Parent nodes are larger than children.	Parent nodes are smaller than children.
Usage	Used when you need the largest element quickly.	Used when you need the smallest element quickly.
Application	Useful in algorithms like heapsort, to find the maximum element.	Useful in algorithms like Dijkstra's, to find the minimum distance.
Implementation	Often implemented using arrays, where the root element is at index 0 & largest.	Often implemented using arrays, where the root element is at index 0 & smallest.
Priority Queue	In a priority queue implementation, elements are prioritized by largest value.	In a priority queue implementation, elements are prioritized by smallest value.
Structure	Appears as a complete binary tree where every level, except possibly the last, is fully filled, & all nodes are as far left as possible, with the root being the max value.	Appears as a complete binary tree where every level, except possibly the last, is fully filled, & all nodes are as far left as possible, with the root being the min value.

Internal Implementation of Min-Heap Data Structure

A min heap is a complete binary tree. This means it's almost entirely filled; every level except possibly the last is fully packed, and the last level has all its nodes as far left as possible.

Here's a closer look at how this structure is typically built and maintained:

Complete Binary Tree: Every new element is added at the farthest left open spot, keeping the tree balanced.
Parent-Child Relationship: Each parent node has a value less than or equal to its child nodes. This is the key rule that makes it a min heap.
Array Representation: Although it's a tree, a min heap is often stored in an array. The element at index 0 is the root (smallest element), and for any given element at index i, its children are at indices 2i + 1 and 2i + 2.
Heapify-Up Process: When a new element is added, it might violate the min heap property. So, it's compared to its parent, and if it's smaller, they swap places. This process continues until the min heap property is restored.
Heapify-Down Process: When the root element is removed (which is the smallest), the last element in the heap is temporarily moved to the root. This might violate the min heap property, so it's compared to its children and swapped with the smaller one if necessary. This process repeats until the tree is a min heap again.

This internal setup allows min heaps to efficiently maintain their order, ensuring the smallest element is always easy to access. It's a clever combination of tree structure principles and array storage that makes min heaps a powerful tool in many algorithmic scenarios.

Operations on Min-Heap Data Structure & Their Implementation

Min heaps let you perform a few key operations efficiently. Here's a breakdown of these operations:

Insertion

Adding a new element to a min heap. The element is initially added at the end to maintain the complete binary tree structure. Then, we "heapify-up" to ensure the min heap property is preserved, swapping the new element with its parent until it's no longer smaller than its parent.

Steps for Insertion

Add the New Element: Place the new element at the end of the heap to maintain the complete binary tree structure.
Heapify-Up: Compare the new element with its parent. If the new element is smaller, swap them. Repeat this step until the new element is in a position where it's larger than its parent or it becomes the root.

Let's see how this operation is implemented in C++, Java, Python, and C#.

C++
Java
Python
C#

C++

#include <iostream>
#include <vector>
#include <algorithm>

void insertMinHeap(std::vector<int>& heap, int value) {
    heap.push_back(value); // Step 1: Add the new element
    int index = heap.size() - 1; // Get the index of the new element

    // Step 2: Heapify-Up
    while (index > 0 && heap[index] < heap[(index - 1) / 2]) {
        // Swap with parent if smaller
        std::swap(heap[index], heap[(index - 1) / 2]);
        index = (index - 1) / 2; // Move up to the parent index
    }
}

int main() {
    std::vector<int> minHeap;
    insertMinHeap(minHeap, 5);
    insertMinHeap(minHeap, 3);
    insertMinHeap(minHeap, 10);

    for (int num : minHeap) {
        std::cout << num << " ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;

public class MinHeap {
    private ArrayList<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }

    public void insert(int value) {
        heap.add(value); // Step 1: Add the new element
        int index = heap.size() - 1; // Get the index of the new element

        // Step 2: Heapify-Up
        while (index > 0 && heap.get(index) < heap.get((index - 1) / 2)) {
            // Swap with parent if smaller
            int temp = heap.get(index);
            heap.set(index, heap.get((index - 1) / 2));
            heap.set((index - 1) / 2, temp);
            index = (index - 1) / 2; // Move up to the parent index
        }
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.insert(5);
        minHeap.insert(3);
        minHeap.insert(10);

        System.out.println(minHeap.heap);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

import heapq

min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 10)

print(min_heap)

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

public class MinHeap {
    private List<int> heap;

    public MinHeap() {
        heap = new List<int>();
    }

    public void Insert(int value) {
        heap.Add(value); // Step 1: Add the new element
        int index = heap.Count - 1; // Get the index of the new element

        // Step 2: Heapify-Up
        while (index > 0 && heap[index] < heap[(index - 1) / 2]) {
            // Swap with parent if smaller
            int temp = heap[index];
            heap[index] = heap[(index - 1) / 2];
            heap[(index - 1) / 2] = temp;
            index = (index - 1) / 2; // Move up to the parent index
        }
    }
}

class Program {
    static void Main() {
        MinHeap minHeap = new MinHeap();
        minHeap.Insert(5);
        minHeap.Insert(3);
        minHeap.Insert(10);

        foreach (int item in minHeap.heap) {
            Console.WriteLine(item);
        }
    }
}

Output

3 5 10

Deletion

Specifically, deleting the root (the smallest element). After removing the root, the last element in the heap is placed at the root, and then we "heapify-down" to restore the min heap property. This means swapping it with the smaller of its children until it finds its correct position.

Steps for Deletion

Remove the Root: Replace the root of the heap with the last element in the heap.
Heapify-Down: Compare the new root with its children. If it's larger than one of its children, swap it with the smaller child. Repeat this step until the new root is smaller than its children or it becomes a leaf.

Now, let's look at how this operation is implemented in C++, Java, Python, and C#.

C++
Java
Python
C#

C++


#include <iostream>
#include <vector>
#include <algorithm>

void heapifyDown(std::vector<int>& heap, int index) {
    int size = heap.size();
    int smallest = index;
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;

    if (leftChild < size && heap[leftChild] < heap[smallest])
        smallest = leftChild;

    if (rightChild < size && heap[rightChild] < heap[smallest])
        smallest = rightChild;

    if (smallest != index) {
        std::swap(heap[index], heap[smallest]);
        heapifyDown(heap, smallest);
    }
}

void deleteRoot(std::vector<int>& heap) {
    int lastElement = heap.back();
    heap[0] = lastElement;
    heap.pop_back();
    heapifyDown(heap, 0);
}

int main() {
    std::vector<int> minHeap = {3, 5, 10};
    deleteRoot(minHeap);

    for (int num : minHeap) {
        std::cout << num << " ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java


import java.util.ArrayList;

public class MinHeap {
    private ArrayList<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }

    private void heapifyDown(int index) {
        int smallest = index;
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;

        if (leftChild < heap.size() && heap.get(leftChild) < heap.get(smallest))
            smallest = leftChild;

        if (rightChild < heap.size() && heap.get(rightChild) < heap.get(smallest))
            smallest = rightChild;

        if (smallest != index) {
            int temp = heap.get(index);
            heap.set(index, heap.get(smallest));
            heap.set(smallest, temp);
            heapifyDown(smallest);
        }
    }

    public void deleteRoot() {
        int lastElement = heap.get(heap.size() - 1);
        heap.set(0, lastElement);
        heap.remove(heap.size() - 1);
        heapifyDown(0);
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.heap.add(3);
        minHeap.heap.add(5);
        minHeap.heap.add(10);
        minHeap.deleteRoot();

        System.out.println(minHeap.heap);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

import heapq

min_heap = [3, 5, 10]
heapq.heappop(min_heap)  # Directly removes the smallest element, which is the root

print(min_heap)

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

public class MinHeap {
    private List<int> heap;

    public MinHeap() {
        heap = new List<int>();
    }

    private void HeapifyDown(int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < heap.Count && heap[left] < heap[smallest])
            smallest = left;

        if (right < heap.Count && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != index) {
            int temp = heap[index];
            heap[index] = heap[smallest];
            heap[smallest] = temp;
            HeapifyDown(smallest);
        }
    }

    public int RemoveMin() {
        if (heap.Count == 0) {
            throw new InvalidOperationException("Heap is empty");
        }

        int root = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);

        if (heap.Count > 0) {
            HeapifyDown(0);
        }

        return root;
    }

    // Just for demonstration, prints the elements in the array that represents the min heap
    public void PrintHeap() {
        foreach (int item in heap) {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        MinHeap minHeap = new MinHeap();
        // Assuming heap is already built and contains elements
        minHeap.heap.AddRange(new List<int> { 1, 3, 6, 5, 9, 8 });

        Console.WriteLine("Min Heap before deletion:");
        minHeap.PrintHeap();

        int min = minHeap.RemoveMin();
        Console.WriteLine($"Removed the smallest element: {min}");

        Console.WriteLine("Min Heap after deletion:");
        minHeap.PrintHeap();
    }
}

Output

5 10

Peek

The peek operation in a min heap is quite straightforward and involves no steps for adjustment or restructuring of the heap. This operation simply returns the element at the root of the heap, which, due to the properties of the min heap, is the smallest element in the heap.

C++
Java
Python
C#

C++

#include <iostream>
#include <vector>

int peek(const std::vector<int>& heap) {
    if (!heap.empty()) {
        return heap[0];  // The root element, which is the smallest
    }
    throw std::runtime_error("Heap is empty");
}

int main() {
    std::vector<int> minHeap = {3, 5, 10};
    std::cout << "The smallest number in the heap is: " << peek(minHeap) << std::endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;

public class MinHeap {
    private ArrayList<Integer> heap;

    public MinHeap() {
        heap = new ArrayList<>();
    }

    public int peek() {
        if (!heap.isEmpty()) {
            return heap.get(0);  // The root element, which is the smallest
        }
        throw new IllegalStateException("Heap is empty");
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        minHeap.heap.add(3);
        minHeap.heap.add(5);
        minHeap.heap.add(10);
        System.out.println("The smallest number in the heap is: " + minHeap.peek());
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

import heapq

min_heap = [3, 5, 10]
heapq.heapify(min_heap)  # Ensure min_heap is a heap
print("The smallest number in the heap is:", min_heap[0])

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

public class MinHeap {
    private List<int> heap;

    public MinHeap() {
        heap = new List<int>();
    }

    public int Peek() {
        if (heap.Count > 0) {
            return heap[0];  // The root element, which is the smallest
        }
        throw new InvalidOperationException("Heap is empty");
    }
}

class Program {
    static void Main() {
        MinHeap minHeap = new MinHeap();
        minHeap.heap.AddRange(new List<int> { 3, 5, 10 });
        Console.WriteLine("The smallest number in the heap is: " + minHeap.Peek());
    }
}

Output

The smallest number in the heap is: 3

Heapify

The heapify operation is crucial for maintaining the min-heap property in a binary heap. It ensures that a given node and its descendants comply with the min-heap property, where the parent node is smaller than its children. This operation can be applied in a bottom-up manner starting from the last non-leaf node all the way up to the root node.

C++
Java
Python
C#

C++

#include <iostream>
#include <vector>

void heapify(std::vector<int>& heap, int n, int i) {
    int smallest = i; // Initialize smallest as root
    int left = 2 * i + 1; // left = 2*i + 1
    int right = 2 * i + 2; // right = 2*i + 2

    // If left child is smaller than root
    if (left < n && heap[left] < heap[smallest])
        smallest = left;

    // If right child is smaller than smallest so far
    if (right < n && heap[right] < heap[smallest])
        smallest = right;

    // If smallest is not root
    if (smallest != i) {
        std::swap(heap[i], heap[smallest]);

        // Recursively heapify the affected sub-tree
        heapify(heap, n, smallest);
    }
}

// Function to build a Min-Heap from the given array
void buildMinHeap(std::vector<int>& heap) {
    int n = heap.size();

    // Index of last non-leaf node
    int startIdx = (n / 2) - 1;

    // Perform reverse level order traversal from last non-leaf node and heapify each node
    for (int i = startIdx; i >= 0; i--) {
        heapify(heap, n, i);
    }
}

int main() {
    std::vector<int> heap = {10, 5, 3, 2, 4};

    buildMinHeap(heap);

    std::cout << "Min Heap: ";
    for (int i = 0; i < heap.size(); ++i)
        std::cout << heap[i] << " ";
    std::cout << "\n";

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.Arrays;

public class MinHeap {
    public void heapify(int[] heap, int n, int i) {
        int smallest = i; // Initialize smallest as root
        int left = 2 * i + 1; // left = 2*i + 1
        int right = 2 * i + 2; // right = 2*i + 2

        // If left child is smaller than root
        if (left < n && heap[left] < heap[smallest])
            smallest = left;

        // If right child is smaller than smallest so far
        if (right < n && heap[right] < heap[smallest])
            smallest = right;

        // If smallest is not root
        if (smallest != i) {
            int swap = heap[i];
            heap[i] = heap[smallest];
            heap[smallest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(heap, n, smallest);
        }
    }

    // Function to build a Min-Heap from the given array
    public void buildMinHeap(int[] heap) {
        int n = heap.length;

        // Index of last non-leaf node
        int startIdx = (n / 2) - 1;

        // Perform reverse level order traversal from last non-leaf node and heapify each node
        for (int i = startIdx; i >= 0; i--) {
            heapify(heap, n, i);
        }
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap();
        int[] heapArray = {10, 5, 3, 2, 4};

        minHeap.buildMinHeap(heapArray);

        System.out.println("Min Heap: " + Arrays.toString(heapArray));
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

import heapq

def buildMinHeap(heap):
    heapq.heapify(heap)

heap = [10, 5, 3, 2, 4]
buildMinHeap(heap)

print("Min Heap:", heap)

You can also try this code with Online Python Compiler

Run Code

C#

using System;

public class MinHeap {
    private int[] heap;
    public int Size { get; private set; }

    public MinHeap(int size) {
        heap = new int[size];
        Size = 0;
    }

    private void Heapify(int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < Size && heap[left] < heap[smallest])
            smallest = left;

        if (right < Size && heap[right] < heap[smallest])
            smallest = right;

        if (smallest != i) {
            Swap(ref heap[i], ref heap[smallest]);
            Heapify(smallest);
        }
    }

    public void BuildMinHeap() {
        int startIdx = (Size / 2) - 1;
        for (int i = startIdx; i >= 0; i--) {
            Heapify(i);
        }
    }

    private void Swap(ref int x, ref int y) {
        int temp = x;
        x = y;
        y = temp;
    }

    public void Insert(int element) {
        if (Size == heap.Length)
            throw new InvalidOperationException("Heap is full");

        heap[Size] = element;
        Size++;

        int current = Size - 1;
        while (current > 0 && heap[current] < heap[(current - 1) / 2]) {
            Swap(ref heap[current], ref heap[(current - 1) / 2]);
            current = (current - 1) / 2;
        }
    }

    // Just for demonstration, it prints the elements in the array that represents the min heap
    public void PrintHeap() {
        for (int i = 0; i < Size; i++) {
            Console.Write(heap[i] + " ");
        }
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.Insert(3);
        minHeap.Insert(2);
        minHeap.Insert(1);
        minHeap.Insert(7);
        minHeap.Insert(8);
        minHeap.Insert(4);
        minHeap.Insert(10);
        minHeap.Insert(16);
        minHeap.Insert(12);

        Console.WriteLine("Before building min heap:");
        minHeap.PrintHeap();

        minHeap.BuildMinHeap();

        Console.WriteLine("After building min heap:");
        minHeap.PrintHeap();
    }
}

Output

Min Heap: 2 4 3 5 10

Search

The search operation in a min heap isn't as straightforward as in other data structures because min heaps are primarily optimized for accessing the smallest element, not for searching arbitrary elements. However, you can still perform a search operation by traversing the heap.

C++
Java
Python
C#

C++

#include <iostream>
#include <vector>

bool searchMinHeap(const std::vector<int>& heap, int value) {
    for (int num : heap) {
        if (num == value) {
            return true;  // Value found
        }
    }
    return false;  // Value not found
}

int main() {
    std::vector<int> minHeap = {3, 5, 10, 12, 9};

    int searchValue = 10;
    bool found = searchMinHeap(minHeap, searchValue);
    std::cout << "Value " << searchValue << (found ? " is found" : " is not found") << " in the min heap." << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

import java.util.ArrayList;
import java.util.List;

public class MinHeapSearch {
    public static boolean searchMinHeap(List<Integer> heap, int value) {
        for (int num : heap) {
            if (num == value) {
                return true;  // Value found
            }
        }
        return false;  // Value not found
    }

    public static void main(String[] args) {
        List<Integer> minHeap = new ArrayList<>(List.of(3, 5, 10, 12, 9));

        int searchValue = 10;
        boolean found = searchMinHeap(minHeap, searchValue);
        System.out.println("Value " + searchValue + (found ? " is found" : " is not found") + " in the min heap.");
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

def search_min_heap(heap, value):
    return value in heap

min_heap = [3, 5, 10, 12, 9]

search_value = 10
found = search_min_heap(min_heap, search_value)
print(f"Value {search_value} {'is found' if found else 'is not found'} in the min heap.")

You can also try this code with Online Python Compiler

Run Code

C#

using System;
using System.Collections.Generic;

public class MinHeap {
    private List<int> heap;

    public MinHeap() {
        heap = new List<int>();
    }

    public bool Search(int value) {
        foreach (int num in heap) {
            if (num == value) {
                return true;  // Value found
            }
        }
        return false;  // Value not found
    }
}

class Program {
    static void Main() {
        MinHeap minHeap = new MinHeap();
        minHeap.heap.AddRange(new List<int> { 3, 5, 10, 12, 9 });

        int searchValue = 10;
        bool found = minHeap.Search(searchValue);
        Console.WriteLine($"Value {searchValue} {(found ? "is found" : "is not found")} in the min heap.");
    }
}

Output

Value 10 is found in the min heap.

Advantages of Min-Heap Data Structure

Min heaps are a fundamental data structure in computer science, offering several benefits that make them suitable for a variety of applications:

Efficient Element Access

The most significant advantage of a min heap is the efficient access to the smallest element. With the smallest element always at the root, operations like finding the minimum value are executed in constant time O(1), which is crucial for algorithms that require frequent access to the minimum element.

Dynamic Data Handling

Min heaps are excellent for handling dynamically changing data. They allow for the insertion of new elements and deletion of the minimum element while maintaining the heap property, making them ideal for priority queues where the set of tasks or priorities can change over time.

Simplified Memory Management

Since min heaps can be implemented using arrays, they offer a compact and straightforward way to manage memory. This array-based implementation eliminates the need for pointers, reducing memory usage and overhead.

Balanced Structure

The complete binary tree structure of min heaps ensures that the tree remains balanced. This balance is crucial for keeping operations like insertion and deletion efficient, with their time complexities being O(logn) where n is the number of elements in the heap.

Algorithmic Efficiency

Min heaps are key components in several efficient algorithms, such as Dijkstra's algorithm for shortest paths and Prim's algorithm for minimum spanning trees. Their ability to quickly provide the smallest element makes these algorithms much more efficient.

Streamlined Sorting

Heapsort, a comparison-based sorting algorithm, utilizes the structure of min heaps to sort elements. By iteratively removing the smallest element from the heap and rebuilding it, heapsort achieves a time complexity of O(nlogn), competitive with other efficient sorting algorithms like quicksort and mergesort.

Priority Queue Implementation

Perhaps the most common use of min heaps is in implementing priority queues. In a priority queue, elements are processed based on their priority rather than the order in which they were added. Min heaps efficiently support the operations required for priority queues, such as inserting elements with a specific priority and removing the element with the highest (or in this case, the lowest) priority.

Frequently Asked Questions

Can a min heap contain duplicate values?

Yes, a min heap can contain duplicate values. The heap property only requires that each parent node be smaller than or equal to its child nodes, which allows for the inclusion of duplicates.

How do you update a value in a min heap?

To update a value in a min heap, you first need to find the index of the value you want to update. After updating the value, you may need to restore the heap property. If the new value is smaller, you'll apply the heapify-up process; if it's larger, you'll use the heapify-down process.

Is a min heap always a balanced binary tree?

A min heap is always a complete binary tree, meaning it is as balanced as possible. Every level, except possibly the last, is fully filled, and all nodes in the last level are as far left as possible. This structure ensures that the tree remains balanced, keeping operations efficient.

Conclusion

In this article, we've learned the concept of min heaps, from their definition and uses to their implementation in various programming languages. We explored the purpose and benefits of min heaps, saw how they're implemented in C++, Java, Python, and C#, and looked into key operations like insertion, deletion, and searching within these data structures. We also compared min heaps with max heaps to highlight their differences and discussed the internal workings and advantages of min heaps.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.