Heapify operation on Min-Heap Data Structure

3. Peek operation on Min-Heap Data Structure:

5. Search operation on Min-Heap Data Structure:

A heapify operation can be used to create a min heap from an unsorted array. This is done by starting at the last non-leaf node and repeatedly performing the “bubble down” operation until all nodes satisfy the heap property.

Heapify operation in Min Heap

Implementation of Heapify operation in Min-Heap:

C++

#include <iostream>
#include <vector>
using namespace std;

void minHeapify(vector<int> &arr, int i, int n) {
    int smallest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] < arr[smallest])
        smallest = l;

    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        minHeapify(arr, smallest, n);
    }
}

int main() {
    vector<int> arr = {10, 5, 15, 2, 20, 30};

    cout << "Original array: ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    // Perform heapify operation on min-heap
    for (int i = arr.size()/2 - 1; i >= 0; i--)
        minHeapify(arr, i, arr.size());

    cout << "\nMin-Heap after heapify operation: ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    return 0;
}

Java

// Java code of Heapify operation in Min-Heap

import java.util.Arrays;
import java.util.List;

public class Main {
    // Function to maintain the min-heap property of the heap rooted at index 'i'
    public static void minHeapify(List<Integer> arr, int i, int n) {
        // Assume the root is the smallest element initially
        int smallest = i;
        // Calculate the indices of the left and right child of the current node
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        // Compare the left child with the current smallest
        if (l < n && arr.get(l) < arr.get(smallest))
            smallest = l;

        // Compare the right child with the current smallest
        if (r < n && arr.get(r) < arr.get(smallest))
            smallest = r;

        // If the current node is not the smallest, swap it with the smallest child
        if (smallest != i) {
            int temp = arr.get(i);
            arr.set(i, arr.get(smallest));
            arr.set(smallest, temp);
            // Recursively heapify the subtree rooted at the smallest child
            minHeapify(arr, smallest, n);
        }
    }

    public static void main(String[] args) {
        // Create a list representing the array
        List<Integer> arr = Arrays.asList(10, 5, 15, 2, 20, 30);

        System.out.print("Original array: ");
        // Print the original array
        for (int i = 0; i < arr.size(); i++)
            System.out.print(arr.get(i) + " ");

        // Perform heapify operation on the min-heap
        // Start from the last non-leaf node and go up to the root of the tree
        for (int i = arr.size() / 2 - 1; i >= 0; i--)
            minHeapify(arr, i, arr.size());

        System.out.print("\nMin-Heap after heapify operation: ");
        // Print the min-heap after heapify operation
        for (int i = 0; i < arr.size(); i++)
            System.out.print(arr.get(i) + " ");
    }
}

Python

def minHeapify(arr, i, n):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] < arr[smallest]:
        smallest = left

    if right < n and arr[right] < arr[smallest]:
        smallest = right

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        minHeapify(arr, smallest, n)

if __name__ == "__main__":
    arr = [10, 5, 15, 2, 20, 30]

    print("Original array:", arr)

    # Perform heapify operation on a min-heap
    for i in range(len(arr) // 2 - 1, -1, -1):
        minHeapify(arr, i, len(arr))

    print("Min-Heap after heapify operation:", arr)

using System;
using System.Collections.Generic;

class GFG
{
    // Function to perform the minHeapify operation on a min-heap.
    static void MinHeapify(List<int> arr, int i, int n)
    {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Compare the left child with the current smallest node.
        if (left < n && arr[left] < arr[smallest])
            smallest = left;
        // Compare the right child with the current smallest node.
        if (right < n && arr[right] < arr[smallest])
            smallest = right;
        // If the current node is not the smallest
        // swap it with the smallest child.
        if (smallest != i)
        {
            int temp = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = temp;
            // Recursively call minHeapify on the affected subtree.
            MinHeapify(arr, smallest, n);
        }
    }
    static void Main(string[] args)
    {
        List<int> arr = new List<int> { 10, 5, 15, 2, 20, 30 };
        Console.Write("Original array: ");
        foreach (int num in arr)
            Console.Write(num + " ");
        // Perform heapify operation on the min-heap.
        for (int i = arr.Count / 2 - 1; i >= 0; i--)
            MinHeapify(arr, i, arr.Count);
        Console.Write("\nMin-Heap after heapify operation: ");
        foreach (int num in arr)
            Console.Write(num + " ");
    }
}

Javascript

// Define a function to perform min-heapify operation on an array
function minHeapify(arr, i, n) {
    let smallest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;

    // Check if left child is smaller than the current smallest element
    if (l < n && arr[l] < arr[smallest])
        smallest = l;

    // Check if right child is smaller than the current smallest element
    if (r < n && arr[r] < arr[smallest])
        smallest = r;

    // If the smallest element is not the current element, swap them
    if (smallest !== i) {
        [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
        minHeapify(arr, smallest, n);
    }
}

// Main function
function main() {
    const arr = [10, 5, 15, 2, 20, 30];

    // Print the original array
    console.log("Original array: " + arr.join(" "));

    // Perform heapify operation on the min-heap
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--)
        minHeapify(arr, i, arr.length);

    // Print the min-heap after heapify operation
    console.log("Min-Heap after heapify operation: " + arr.join(" "));
}

// Call the main function to start the process
main();

Output

Original array: 10 5 15 2 20 30 
Min-Heap after heapify operation: 2 5 15 10 20 30

The time complexity of heapify in a min-heap is O(n).

Introduction to Min-Heap – Data Structure and Algorithm Tutorials

A Min-Heap is defined as a type of Heap Data Structure in which each node is smaller than or equal to its children.

The heap data structure is a type of binary tree that is commonly used in computer science for various purposes, including sorting, searching, and organizing data.

Introduction to Min-Heap – Data Structure and Algorithm Tutorials

Purpose and Use Cases of Min-Heap:

Implementing Priority Queue: One of the primary uses of the heap data structure is for implementing priority queues.
Dijkstra’s Algorithm: Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between two nodes in a graph. A min heap can be used to keep track of the unvisited nodes with the smallest distance from the source node.
Sorting: A min heap can be used as a sorting algorithm to efficiently sort a collection of elements in ascending order.
Median finding: A min heap can be used to efficiently find the median of a stream of numbers. We can use one min heap to store the larger half of the numbers and one max heap to store the smaller half. The median will be the root of the min heap.

Heapify operation on Min-Heap Data Structure

Implementation of Heapify operation in Min-Heap:

Introduction to Min-Heap – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us