Implementation of Heap Sort
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int l = 2 * i + 1;
// right = 2*i + 2
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 largest
// so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int N)
{
// Build heap (rearrange array)
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--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver's code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
cout << "Sorted array is \n";
printArray(arr, N);
}
// Heap Sort in C
#include <stdio.h>
// Function to swap the position of two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
{
// Find largest among root,
// left child and right child
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int left = 2 * i + 1;
// right = 2*i + 2
int right = 2 * i + 2;
// If left child is larger than root
if (left < N && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest
// so far
if (right < N && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying
// if root is not largest
// If largest is not root
if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest);
}
}
// Main function to do heap sort
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 root element
// to get highest element at
// root again
heapify(arr, i, 0);
}
}
// A utility function to print array of size n
void printArray(int arr[], int N)
{
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver's code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
}
// This code is contributed by _i_plus_plus_.
// Java program for implementation of Heap Sort
public class HeapSort {
public void sort(int arr[])
{
int N = arr.length;
// Build heap (rearrange array)
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--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int N, 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 < N && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, N, largest);
}
}
/* A utility function to print array of size n */
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's code
public static void main(String args[])
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = arr.length;
// Function call
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
// C# program for implementation of Heap Sort
using System;
public class HeapSort {
public void sort(int[] arr)
{
int N = arr.Length;
// Build heap (rearrange array)
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--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int[] arr, int N, 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 < N && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, N, largest);
}
}
/* A utility function to print array of size n */
static void printArray(int[] arr)
{
int N = arr.Length;
for (int i = 0; i < N; ++i)
Console.Write(arr[i] + " ");
Console.Read();
}
// Driver's code
public static void Main()
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
int N = arr.Length;
// Function call
HeapSort ob = new HeapSort();
ob.sort(arr);
Console.WriteLine("Sorted array is");
printArray(arr);
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
// JavaScript program for implementation
// of Heap Sort
function sort( arr)
{
var N = arr.length;
// Build heap (rearrange array)
for (var i = Math.floor(N / 2) - 1; i >= 0; i--)
heapify(arr, N, i);
// One by one extract an element from heap
for (var i = N - 1; i > 0; i--) {
// Move current root to end
var temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function heapify(arr, N, i)
{
var largest = i; // Initialize largest as root
var l = 2 * i + 1; // left = 2*i + 1
var r = 2 * i + 2; // right = 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 largest so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
var swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, N, largest);
}
}
/* A utility function to print array of size n */
function printArray(arr)
{
var N = arr.length;
for (var i = 0; i < N; ++i)
document.write(arr[i] + " ");
}
var arr = [12, 11, 13, 5, 6, 7];
var N = arr.length;
sort(arr);
document.write( "Sorted array is");
printArray(arr, N);
// This code is contributed by SoumikMondal
<?php
// Php program for implementation of Heap Sort
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function heapify(&$arr, $N, $i)
{
$largest = $i; // Initialize largest as root
$l = 2*$i + 1; // left = 2*i + 1
$r = 2*$i + 2; // right = 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 largest so far
if ($r < $N && $arr[$r] > $arr[$largest])
$largest = $r;
// If largest is not root
if ($largest != $i)
{
$swap = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $swap;
// Recursively heapify the affected sub-tree
heapify($arr, $N, $largest);
}
}
// main function to do heap sort
function heapSort(&$arr, $N)
{
// Build heap (rearrange array)
for ($i = $N / 2 - 1; $i >= 0; $i--)
heapify($arr, $N, $i);
// One by one extract an element from heap
for ($i = $N-1; $i > 0; $i--)
{
// Move current root to end
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
// call max heapify on the reduced heap
heapify($arr, $i, 0);
}
}
/* A utility function to print array of size n */
function printArray(&$arr, $N)
{
for ($i = 0; $i < $N; ++$i)
echo ($arr[$i]." ") ;
}
// Driver's program
$arr = array(12, 11, 13, 5, 6, 7);
$N = sizeof($arr)/sizeof($arr[0]);
// Function call
heapSort($arr, $N);
echo 'Sorted array is ' . "\n";
printArray($arr , $N);
// This code is contributed by Shivi_Aggarwal
?>
# Python program for implementation of heap Sort
# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, N, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < N and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < N and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, N, largest)
# The main function to sort an array of given size
def heapSort(arr):
N = len(arr)
# Build a maxheap.
for i in range(N//2 - 1, -1, -1):
heapify(arr, N, i)
# One by one extract elements
for i in range(N-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# Driver's code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
# Function call
heapSort(arr)
N = len(arr)
print("Sorted array is")
for i in range(N):
print("%d" % arr[i], end=" ")
# This code is contributed by Mohit Kumra
Output
Sorted array is 5 6 7 11 12 13
Heap Sort – Data Structures and Algorithms Tutorials
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.