Example 1: Heap sort in c++
#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 (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
Example 2: heap sort
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
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 and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
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);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
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);
}
Example 3: heap sort
// @see https://www.youtube.com/watch?v=H5kAcmGOn4Q
function heapify(list, size, index) {
let largest = index;
let left = index * 2 + 1;
let right = left + 1;
if (left < size && list[left] > list[largest]) {
largest = left;
}
if (right < size && list[right] > list[largest]) {
largest = right;
}
if (largest !== index) {
[list[index], list[largest]] = [list[largest], list[index]];
heapify(list, size, largest);
}
return list;
}
function heapsort(list) {
const size = list.length;
let index = ~~(size / 2 - 1);
let last = size - 1;
while (index >= 0) {
heapify(list, size, --index);
}
while (last >= 0) {
[list[0], list[last]] = [list[last], list[0]];
heapify(list, --last, 0);
}
return list;
}
heapsort([4, 7, 2, 6, 4, 1, 8, 3]);
Example 4: heapsort
Implementation of heap sort in C++:
#include <bits/stdc++.h>
using namespace std;
// To heapify a subtree rooted with node i which is
// Heapify:- A process which helps regaining heap properties in tree after removal
void heapify(int A[], int n, int i)
{
int largest = i; // Initialize largest as root
int left_child = 2 * i + 1; // left = 2*i + 1
int right_child = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (left_child < n && A[left_child] > A[largest])
largest = left_child;
// If right child is larger than largest so far
if (right_child < n && A[right_child] > A[largest])
largest = right_child;
// If largest is not root
if (largest != i) {
swap(A[i], A[largest]);
// Recursively heapify the affected sub-tree
heapify(A, n, largest);
}
}
// main function to do heap sort
void heap_sort(int A[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(A, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(A[0], A[i]);
// call max heapify on the reduced heap
heapify(A, i, 0);
}
}
/* A function to print sorted Array */
void printArray(int A[], int n)
{
for (int i = 0; i < n; ++i)
cout << A[i] << " ";
cout << "\n";
}
// Driver program
int main()
{
int A[] = { 22, 19, 3, 25, 26, 7 }; // array to be sorted
int n = sizeof(A) / sizeof(A[0]); // n is size of array
heap_sort(A, n);
cout << "Sorted array is \n";
printArray(A, n);
}
Example 5: heap sort heapify and max heap in binary tree
Implementation of heap sort in C:
#include <stdio.h>
int main()
{
int heap[10], array_size, i, j, c, root, temporary;
printf("\n Enter size of array to be sorted :");
scanf("%d", &array_size);
printf("\n Enter the elements of array : ");
for (i = 0; i < array_size; i++)
scanf("%d", &heap[i]);
for (i = 1; i < array_size; i++)
{
c = i;
do
{
root = (c - 1) / 2;
if (heap[root] < heap[c]) /* to create MAX heap array */
{ // if child is greater than parent swap them
temporary = heap[root]; // as structure is of complete binary tree
heap[root] = heap[c]; // it took logn steps to reach from root to leaf
heap[c] = temporary;
}
c = root;
} while (c != 0);
}
printf("Heap array : ");
for (i = 0; i < array_size; i++)
printf("%d\t ", heap[i]); //printing the heap array
for (j = array_size - 1; j >= 0; j--)
{
temporary = heap[0];
heap[0] = heap[j] ; /* swap max element with rightmost leaf element */
heap[j] = temporary;
root = 0;
do
{
c = 2 * root + 1; /* left node of root element */
if ((heap[c] < heap[c + 1]) && c < j-1)
c++;
if (heap[root]<heap[c] && c<j) /* again rearrange to max heap array */
{
temporary = heap[root];
heap[root] = heap[c];
heap[c] = temporary;
}
root = c;
} while (c < j);
}
printf("\n The sorted array is : ");
for (i = 0; i < array_size; i++)
printf("\t %d", heap[i]);
}
Example 6: heapsort
#include <iostream>
using namespace std;
void swap(int*,int*);
void heapify(int arr[],int n,int index)
{
int left=2*index+1;
int right=left+1;
int max=index;
if(left<n&&arr[left]>arr[max])
{
max=left;
}
if(right<n&&arr[right]>arr[max])
{
max=right;
}
if(index!=max)
{
swap(&arr[index],&arr[max]);
heapify(arr,n,max);
}
}
void buildheap(int arr[],int n)
{
for(int i=(n/2);i>=0;i--)
{
heapify(arr,n,i);
}
}
void heapsort(int arr[],int n)
{
buildheap(arr,n);
int l=n-1;
while(l>0)
{
swap(&arr[0],&arr[l]);
l--;
n--;
heapify(arr,n,0);
}
}
void disp(int arr[],int n)
{
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
int n;
cout<<"enter the size of the array:"<<endl;
cin>>n;
int a[n];
cout<<"enter the elements of the array:"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"array before sorting:"<<endl;
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
//buildheap(a,n);
//disp(a,n);
cout<<"array after sorting:"<<endl;
heapsort(a,n);
disp(a,n);
return 0;
}
void swap(int*a,int*b)
{
int temp=*a;
*a=*b;
*b=temp;
}