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 Max Heap

So, you want to build a max heap in C, C++, Python and Java? Well, it's actually pretty straightforward! The first step is to create an array that will store your values. Once you've done that, you'll want to begin populating the array with your data. To build a max heap, you'll need to ensure that every parent node has a higher value than its children. One easy way to do this is by starting at the middle of the array and working backwards through each parent-child pair, swapping values as needed. Finally, once all of your values have been added and arranged correctly within the heap, you can simply print out your newly-created max heap for testing purposes. And there you have it – a simple program for building a max heap in C!

(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 largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

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

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

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    buildMaxHeap(arr, n);

    printf("Max Heap: ");
    printArray(arr, n);

    return 0;
}
Output:-
Original array: 12 11 13 5 6 7
Max Heap: 13 12 7 5 6 11

(b.) C++ Code

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

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

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

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

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

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

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

void printArray(const vector<int>& arr) {
    for (int i : arr)
        cout << i << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();

    cout << "Original array: ";
    printArray(arr);

    buildMaxHeap(arr, n);

    cout << "Max Heap: ";
    printArray(arr);

    return 0;
}
Output:-
Original array: 12 11 13 5 6 7
Max Heap: 13 12 7 5 6 11

(c.) Python Code

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

def printArray(arr):
    for i in arr:
        print(i, end=" ")
    print()

arr = [12, 11, 13, 5, 6, 7]
print("Original array:", end=" ")
printArray(arr)

buildMaxHeap(arr)
print("Max Heap:", end=" ")
printArray(arr)
Output:-
Original array: 12 11 13 5 6 7
Max Heap: 13 12 7 5 6 11

(d.) Java Code

import java.util.Arrays;

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

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

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

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

            heapify(arr, n, largest);
        }
    }

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

    public static void printArray(int arr[]) {
        for (int i : arr)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        System.out.print("Original array: ");
        printArray(arr);

        buildMaxHeap(arr);

        System.out.print("Max Heap: ");
        printArray(arr);
    }
}
Output:-
Original array: 12 11 13 5 6 7
Max Heap: 13 12 7 5 6 11

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎