Implementation of Heap Sort
C++
// C++ program for implementation of Heap Sort
#include
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);
}
C
// Heap Sort in C
#include
// 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
// 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#
// 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
// 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
$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
?>
Python3
# 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...