The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Build a Min Heap

Hey there, so if you're looking to build a min heap in C programming language, you can do so by implementing the heapify algorithm. To begin with, create an array and insert the values into it. Once done, start building your heap by focusing on the non-leaf nodes first; traverse through half of the array backwards and use the heapify algorithm to swap any node that violates the min-heap property with its child nodes until none of them violate it anymore. This will ensure that all branches below every node also follow the min-heap property, allowing us to maintain a minimum value at the root node throughout our program execution. Finally, your min heap is built and you can access its elements in ascending order as per your requirement.

(a.) C Code

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

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

void buildMinHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void printHeap(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("
");
}

int main() {
    int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    buildMinHeap(arr, n);

    printf("MinHeap: ");
    printHeap(arr, n);

    return 0;
}
Output:-
MinHeap: 3 5 9 6 8 20 10 12 18 9

(b.) C++ Code

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

void heapify(vector<int>& arr, int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

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

void buildMinHeap(vector<int>& arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

void printHeap(const vector<int>& arr, int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
    int n = arr.size();

    buildMinHeap(arr, n);

    cout << "MinHeap: ";
    printHeap(arr, n);

    return 0;
}
Output:-
MinHeap: 3 5 9 6 8 20 10 12 18 9

(c.) Python Code

def heapify(arr, n, i):
    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]
        heapify(arr, n, smallest)

def buildMinHeap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def printHeap(arr):
    print("MinHeap:", arr)

arr = [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]
buildMinHeap(arr)
printHeap(arr)
Output:-
MinHeap: [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]

(d.) Java Code

import java.util.Arrays;

public class MinHeap {
    public void heapify(int arr[], int n, int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

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

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

        if (smallest != i) {
            int swap = arr[i];
            arr[i] = arr[smallest];
            arr[smallest] = swap;

            heapify(arr, n, smallest);
        }
    }

    public void buildMinHeap(int arr[]) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
    }

    public void printHeap(int arr[]) {
        int n = arr.length;
        System.out.print("MinHeap: ");
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
        MinHeap minHeap = new MinHeap();
        minHeap.buildMinHeap(arr);
        minHeap.printHeap(arr);
    }
}
Output:-
MinHeap: [3, 5, 9, 6, 8, 20, 10, 12, 18, 9]

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎