Heap Sort

Heap Sort

 

Heap Sort is a efficient and popular sorting algorithm in programming. Heap is a complete binary tree and this  tree in which the node can have the atmost two children. A complete binary tree is a binary tree in having levels except the last level, that is leaf node, should be completely filled.

The concept of this sort is to eliminate the elements one by one from the heap of the list, and then insert them into the sorted part of the list.

 

 

Algorithm

HeapSort(arr)  
BuildMaxHeap(arr)  
for i = length(arr) to 2  
    swap arr[1] with arr[i]  
        heap_size[arr] = heap_size[arr] ? 1  
        MaxHeapify(arr,1)  
End

Working of Heap sort Algorithm

 

Working of the Heapsort Algorithm.

In heap sort generally, there are two phases in the sorting of elements. By using the heap sort algorithm, they are following

In first step the creation of a heap by adjusting the elements of the array. And then remove the root element of the heap repeately by shifting it to the end of the array, and after that store the heap structure with the remaining elements.

 

 

Example of Heap Sort

 

Suppose we take an unsorted array and try to sort it using heap.

 

Heap Sort Algorithm

 

 

Firstly, we have to construct a heap from the array and convert it into max heap.

 

Heap Sort Algorithm

 

 

 

After converting the given heap into max heap, the array elements are

 

 

Heap Sort Algorithm

 

 

Next, we delete the root element that is 89 from the max heap. To remove this node, we have to swap it with the last node that is 11. After removing the root element,  again have to heapify it to convert it into max heap.

 

 

Heap Sort Algorithm

 

 

 

After swapping the array element 89 with 11, and converting the heap into the max-heap, then the elements of array are as follows

 

 

Heap Sort Algorithm

 

 

 

In the next step  again we delete the root element 81 from the max heap. To delete this node we have to swap it with the 54 i.e last node. After deleting the root element, heapify is convert into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the array element 81 with 54 and converting the heap into max-heap, the elements of array are  given below-

 

 

Heap Sort Algorithm

 

 

In the next step, we have to remove the  76 i.e. root element from the max heap again. To delete this node, we have to swap it with the 9 i.e.last node. After deleting the root element, we again have to heapify it to convert it into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the element 76 with 9 and converting the heap into max-heap, the elements of array are given below

 

 

Heap Sort Algorithm

 

 

After that, again we have to remove the 54 i.e root element from the max heap. To remove this node, swap it with the 14 i.e last node .After deleting the root element,heapify is convert  into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the element 54 with 14 and converted the heap into max-heap, the elements of array are given below

 

 

Heap Sort Algorithm

 

 

In the next step, we have to remove the 22 i.e  root element from the max heap. To remove this node, swap it with the  11i i.e last node.After removing the root element, heapify it to convert it into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the array element 22 with 11 and converting the heap into max-heap, the elements of array are given below –

 

 

Heap Sort Algorithm

 

 

In the next step, again we have to remove the 14 i.e.root element from the max heap. To remove this node, swap it with the 9 i.e last node. After removing the root element, heapify it to convert it into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the array element 14 with 9 and converting the heap into max-heap, the elements of array are  given by-

 

 

Heap Sort Algorithm

 

 

In the next step, again we have to remove the 11 i.e root element from the max heap. To remove this node,swap it with the 9 i.e. last node. After removing the root element, heapify it to convert it into max heap.

 

 

Heap Sort Algorithm

 

 

After swapping the array element 11 with 9 the elements of array are given below-

 

 

Heap Sort Algorithm

 

 

 

Heap have only one element left. After removing it, heap will be empty.

 

 

Heap Sort Algorithm

 

 

After completion of sorting the array elements are given below –

 

 

Heap Sort Algorithm

 

 

The array is completely sorted.

 

Program of Heap sort in C

#include <stdio.h>

// Function to swapping
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);
  }
}

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

  // Heap sort
  for (int i = n - 1; i >= 0; i--) {
    swap(&arr[0], &arr[i]);

    // Heapify root 
    heapify(arr, i, 0);
  }
}

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

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

  heapSort(arr, n);

  printf("Sorted array is \n");
  printArray(arr, n);
}

Output

Sorted array is 
1 5 6 9 10 12

 

 

Program of Heap sort in C++

#include <iostream>
using namespace std;

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;

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

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

  // Heap sort
  for (int i = n - 1; i >= 0; i--) {
    swap(arr[0], arr[i]);

    heapify(arr, i, 0);
  }
}

// Printing an array
void printArray(int arr[], int n) {
  for (int i = 0; i < n; ++i)
    cout << arr[i] << " ";
  cout << "\n";
}

// Driver code
int main() {
  int arr[] = {1, 12, 9, 5, 6, 10};
  int n = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, n);

  cout << "Sorted array is \n";
  printArray(arr, n);
}

Output

Sorted array is 
1 5 6 9 10 12

Program of Heap sort in Python

def heapify(arr, n, i):
    # largest root 
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

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


def heapSort(arr):
    n = len(arr)

    #  max heap
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        # Swap
        arr[i], arr[0] = arr[0], arr[i]

        # Heapify 
        heapify(arr, i, 0)


arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print("%d " % arr[i], end='')

Output

Sorted array is 
1 5 6 9 10 12

Program of Heap sort in Java

public class HeapSort {

  public void sort(int arr[]) {
    int n = arr.length;

    //  max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    // Heap sort
    for (int i = n - 1; i >= 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // Heapify 
      heapify(arr, i, 0);
    }
  }

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

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

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

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

      heapify(arr, n, largest);
    }
  }

  // Function 
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  // Driver code
  public static void main(String args[]) {
    int arr[] = { 1, 12, 9, 5, 6, 10 };

    HeapSort hs = new HeapSort();
    hs.sort(arr);

    System.out.println("Sorted array is");
    printArray(arr);
  }
}

Output

Sorted array is
1 5 6 9 10 12 

 

 

Heap sort complexity

 

 

1. Time Complexity

Case Time Complexity
Best Case O(n logn)
Average Case O(n log n)
Worst Case O(n log n)

Best Case Complexity

 

  • The best-case time complexity of heapsort is O(n logn).
  • Average Case Complexity – The average case time complexity of heap sort is O(n log n).
  • Worst Case Complexity – The worst-case time complexity of heap sort is O(n log n).

The time complexity of heap sort is O(n logn) .

The height of complete binary tree having n elements is logn.

2. Space Complexity

Space Complexity O(1)
Stable N0
  • The space complexity of Heap sort is O(1).

 

Also read, Bucket Sort

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *