#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 sorting logic by 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--)
{
// swaping logic
temp = arr[0];
arr[0]= arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void main() // defining main()
{
int arr[] = {58, 134, 3, 67, 32, 89, 15, 10,78, 9};
// array initializing with their elements.
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]);
}
#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 largest
if (r < n && arr[r] > arr[largest])
largest = r;
//If root is nor largest
if (largest != i)
{
swap(arr[i], arr[largest]);
//Recursively heapifying 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();
}
}
