×

Courses

Chapters

>
<

Data Structure

Heap Sort | CrackEase

Heap Sort

What is a heap?

A heap is a complete binary tree usually represented as an array. In a max-heap each parent node's value is greater than or equal to its children. Heap Sort uses the heap data structure to sort elements by repeatedly removing the maximum (or minimum) and rebuilding the heap.

High-level Heap Sort steps:

  1. Build a max-heap from the given array.
  2. Swap the root (max) with the last element.
  3. Reduce heap size by one and heapify the root to restore the heap property. Repeat until sorted.
Heapify step 1
Heapify step 2
Code
  
#include <stdio.h>

int temp;

void heapify(int arr[], int size, int i) //declaring functions
{
    int max = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < size && arr[left] > arr[max])
        max = left;

    if (right < size && arr[right] > arr[max])
        max = right;

    if (max != i)
    {
        // performing swapping using temporary variable
        temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;
        heapify(arr, size, max);
    }
}

void heapSort(int arr[], int size) // providing definition to heap sort
{
    int i;
    for (i = size / 2 - 1; i >= 0; i--)
        heapify(arr, size, i);

    for (i = size - 1; i >= 0; i--)
    {
        // swapping root (max) with the last element
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // heapify the reduced heap
        heapify(arr, i, 0);
    }
}

int main() // defining main()
{
    int arr[] = {58, 134, 3, 67, 32, 89, 15, 10, 78, 9};
    int i;
    int size = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, size);

    printf("After Sorting : "); // printing the sorted array
    for (i = 0; i < size; ++i)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}
  

  
#include <iostream>

using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than root
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If root is not largest
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

        // Recursively heapify the sub-tree
        heapify(arr, n, largest);
    }
}

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

    // One by one extract an element from heap
    for (int i = n - 1; i >= 0; i--)
    {
        // Moving current root to end
        swap(arr[0], arr[i]);

        // Calling max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Function to print array
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main()
{
    int arr[] = {58, 134, 3, 67, 32, 89, 15, 10, 78, 9};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    cout << "After Sorting  : ";
    display(arr, n);

}
  

  
public class Main
{
    // Main() for the execution of the program
    public static void main(String args[])
    {
        int a[] = {58, 134, 3, 67, 32, 89, 15, 10, 78, 9};
        int len = a.length;

        Main ob = new Main();
        ob.sort(a);

        System.out.println("After Sorting : ");
        printArray(a);
    }

    public void sort(int a[])
    {
        int len = a.length;

        // Build heap (rearrange array)
        for (int i = len / 2 - 1; i >= 0; i--)
            heapify(a, len, i);

        // One by one extract an element from heap
        for (int i = len - 1; i >= 0; i--)
        {
            // Move current root to end
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;

            // call max heapify on the reduced heap
            heapify(a, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is an index in arr[]. n is size of heap
    void heapify(int a[], int len, int i)
    {
        int largest = i; // Initialize largest as root
        int l = 2*i + 1; // left = 2*i + 1
        int r = 2*i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < len && a[l] > a[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < len && a[r] > a[largest])
            largest = r;

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

            // Recursively heapify the affected sub-tree
            heapify(a, len, largest);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int a[])
    {
        int len = a.length;
        for (int i = 0; i < len; ++i)
            System.out.print(a[i] + " ");
        System.out.println();
    }

}
	

	
After Sorting : 
3 9 10 15 32 58 67 78 89 134
Time Complexity for Heap Sort
BestAverageWorstSpace Complexity
O(n log n)O(n log n)O(n log n)O(1)
Footer Content | CrackEase
→
←