DSA - Sorting Algorithms - Comparision-based Sorting Algorithms - Heap Sort

[akash-coded]

Implement the Heap Sort algortihm

[harsh1997agg]

import java.util.Arrays;

public class heap_sort {

void heapify(int a[],int size,int i) {
	
	int largest=i;
	int left=2*i;
	int right=2*i+1;
	
	if(left<size && a[left]>a[largest]) {
		largest=left;
		
	}
	if(right<size && a[right]>a[largest]) {
		largest=right;
	}
	
	if(largest!=i) {
		int tmp=a[i];
		a[i]=a[largest];
		a[largest]=tmp;
		heapify(a,size,largest);
		
	}
		
}

public void sort(int a[]) {
	
	int size=a.length;
	
	
	//build heap
	for(int i=size/2-1;i>=0;i--) {
		heapify(a,size,i);
	}
	//insert largest at end & again calling Heapify
	for(int i=size-1;i>0;i--) {
		int tmp=a[0];
		a[0]=a[i];
		a[i]=tmp;
		heapify(a,i,0);
	}
	
	
}



public static void main(String[] args) {
	// TODO Auto-generated method stub
	
	int arr[] = { 12, 11, 13, 5, 6, 7 };
	int N = arr.length;
	heap_sort h=new heap_sort();
	h.sort(arr);
	System.out.println(Arrays.toString(arr));

}

}
``

[dhakad-111]

package com.dhakad.week3.tree;

public class HeapSort {

private static int arr[] = { 1, 4, 3, 7, 8, 9, 10 };

public static void main(String[] args) {

	heapSort(arr);

	for (int x : arr) {
		System.out.print(x + " ");
	}
}

private static void heapSort(int[] arr) {
	build_maxHeap(arr);

	int size = arr.length - 1;
	for (int i = size; i >= 1; i--) {
		swap(0, i);
		size--;
		max_heapify(arr, 0, size);
	}

}

private static void build_maxHeap(int[] arr) {
	for (int i = arr.length / 2; i >= 0; i--) {
		max_heapify(arr, i, arr.length - 1);
	}
}

private static void max_heapify(int[] arr, int i, int n) {
	int left = 2 * i;
	int right = 2 * i + 1;
	int max = 0;
	if (left <= n && arr[left] > arr[i]) {
		max = left;
	} else {
		max = i;
	}
	if (right <= n && arr[right] > arr[max]) {
		max = right;
	}
	if (max != i) {
		swap(i, max);
		max_heapify(arr, max, n);
	}
}

private static void swap(int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;

}

}

[Sravan8899]

package heapsort.java;
import java.util.*;

public class Heap {

static void findhepify(int a[],int n,int i){
	int large=i;
	int left=2*i+1;
	int right=2*i+2;
	if(left<n && a[left]>a[large]) 
	{
		large=left;
	}
	if(right<n && a[right]>a[large]) 
	{
		large=right;
	}
	if(large!=i)
	{
		int t=a[i];
		a[i]=a[large];
		a[large]=t;
		
		
		findhepify(a,n,large);
	}
}
static void Hsort(int a[], int n){
	for(int i=n/2-1;i>=0;i--) {
		findhepify(a,n,i);
	}
	for(int j=n-1;j>=0;j--)
	{
		int swap=a[0];
		a[0]=a[j];
		a[j]=swap;
		
		findhepify(a,j,0);
	}
}
static void parr(int a[], int n)  
{  
    for (int k = 0; k < n; k++)  
        System.out.print(a[k] + " ");  
}  
public static void main(String args[]) 
{
int a[]= {40,20,10,87,89};
int n=a.length;
Hsort(a,n);
parr(a,n);
}

}

[PurnaPichuka]

import java.util.Arrays;

public class HeapSort {

    public static void main(String[] args) {
          
           int[] arr = {16,7,22,3,19,9,33};
          
           HeapSort demo = new HeapSort();
          
           demo.sort(arr,arr.length);
           
          System.out.println(Arrays.toString(arr));
    }
    
    public void sort(int[] arr,int size) {
          
           for(int i= size/2-1;i>=0;i--) {	
               
               heapify(arr,size,i);    
          }
          
           for(int i=size-1;i>=0;i--) { 
               
                int temp = arr[0];
               
                arr[0] = arr[i];
               
                arr[i] = temp;
               
               heapify(arr,i,0);               
          }         
    }
    
    public void heapify(int[] arr,int size,int i) {	
          
           int largest = i; 	
          
           int left = (2*i)+1; 	
           int right = (2*i)+2; 
          
           if(left<size && arr[left]> arr[largest]) {                
                largest = left;             
          }
          
           if(right<size && arr[right]> arr[largest]) {              
                largest = right;                
          }
          
           if(largest!= i) {
               
                int temp = arr[i];
                arr[i] = arr[largest];
                arr[largest] = temp;
               
               heapify(arr,size,largest);               
          }     
    }
}

[lingamurthi]

package com.lingu;



public class HeapSort {
	public void sort(int arr[])
	{
		int N = arr.length;

		for (int i = N / 2 - 1; i >= 0; i--)
			heapify(arr, N, i);

	
		for (int i = N - 1; i > 0; i--) {
		
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;

			
			heapify(arr, i, 0);
		}
	}


	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) {
			int swap = arr[i];
			arr[i] = arr[largest];
			arr[largest] = swap;

			
			heapify(arr, N, largest);
		}
	}

	
	static void printArray(int arr[])
	{
		int N = arr.length;

		for (int i = 0; i < N; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

	
	public static void main(String args[])
	{
		int arr[] = { 12, 11, 13, 5, 6, 7 };
		int N = arr.length;

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

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

[AbhishekBilagi]

public class HeapSort {
public static void main(String[] args) {
	int[] arr= {22,13,17,11,10,14,12};
	
	HeapSort hs=new HeapSort();
	hs.sort(arr);
	hs.printArray(arr);
	
}
void sort(int[] arr) {
	int leng=arr.length;
	
	//build heap
	for(int i=leng/2-1;i>=0;i--) {
		heapify(arr,leng,i);
	}
	
	
	//swap the elements and heapify again
	for(int i=leng-1;i>=0;i--) {
		int temp=arr[0];
		arr[0]=arr[i];
		arr[i]=temp;
		heapify(arr,i,0);
	}
}
 void heapify(int[] arr,int n,int i) {
	 
	 //parent index
	 int largest=i;
	 //left child index
	 int li=2*i+1;
	 //right child index
	 int ri=2*i+2;
	 if(li<n && arr[li]>arr[largest]) {
		 largest=li;
	 }
	 if(ri<n && arr[ri]>arr[largest]) {
		 largest=ri;
	 }
	 if(largest!=i) {
		 int temp=arr[i];
		 arr[i]=arr[largest];
		 arr[largest]=temp;
		 heapify(arr,n,largest);
	 }
 }
 void printArray(int[]arr) {
	 for(int i=0;i<arr.length;i++) {
		 System.out.println(arr[i]);
	 }
 }
}

[rrajbanshi]

public class HeapSort {

    public static void heapSort(int arr[]) {
        int N = arr.length;

        buildHeap(arr, N);

        for (int i = N - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public static void buildHeap(int[] arr, int N) {
        for (int i = N / 2 - 1; i >= 0; i--)
            heapify(arr, N, i);
    }

    public static 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) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, N, largest);
        }
    }

    public static void main(String args[]) {
        int arr[] = { 14, 10, 13, 4, 6, 8 };
        heapSort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

[NavneetBais]

public class App {
    public static void main(String[] args) throws Exception {
        int[] a = { -1, 5, 9, 7, 4, 8, 6, 2 };

        heapSort(a, a.length - 1);
        for (int x : a) {
            System.out.print(x);
        }
    }

    // heapify

    // 50
    // / \
    // 30 15
    // / \ /
    // 20 35 10
    public static void heapify(int[] a, int currentElement, int size) {
        int largest = currentElement;
        int left = 2 * currentElement;
        int right = 2 * currentElement + 1;
        if (left <= size && a[left] >= a[largest]) {
            largest = left;
        }
        if (right <= size && a[right] >= a[largest]) {
            largest = right;
        }
        if (largest != currentElement) {
            swap(a, largest, currentElement);
            heapify(a, largest, size);
        }

    }

    public static void swap(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    // 50 30 15 20 35 10
    public static void buildHeap(int[] a, int size) {
        // Build heap (rearrange array)
        for (int i = size / 2; i >= 1; i--)
            heapify(a, size, i);
    }

    public static void heapSort(int[] arr, int size) {
        buildHeap(arr, size);
        for (int i = size; i > 1; i--) {
            // Move current root to end
            int temp = arr[1];
            arr[1] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, 1, i);
        }

    }

}

[atirkey123]

Java

package heapsort;
public class heap {
void heapify(int a[], int n, int i)
{
int lar = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && a[l] > a[lar])
lar = l;


if (r < n && a[r] > a[lar])
lar = r;


if (lar != i) {
int swap = a[i];
a[i] = a[lar];
a[lar] = swap;


heapify(a, n, lar);
}
}

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

for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);

for (int i = n - 1; i > 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;

heapify(a, i, 0);
}
}

static void printaay(int a[])
{
int n = a.length;

for (int i = 0; i < n; ++i)
System.out.print(a[i] + " ");
System.out.println();
}

public static void main(String args[])
{
int a[] = { 12, 11, 13, 5, 6, 7 };
int n = a.length;

heap ob = new heap();
ob.sort(a);

System.out.println("Sorted aay is");
printaay(a);
}
}

[lokeshkumar0007]

Heap Sort

public class HeapSort {
public static void main(String[] args) {
int[] arr= {22,13,17,11,10,14,12};

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

}
void sort(int[] arr) {
int leng=arr.length;

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

//swap the elements and heapify again
for(int i=leng-1;i>=0;i--) {
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
heapify(arr,i,0);
}
}
void heapify(int[] arr,int n,int i) {

//parent index
int largest=i;
//left child index
int li=2i+1;
//right child index
int ri=2i+2;
if(li<n && arr[li]>arr[largest]) {
largest=li;
}
if(ri<n && arr[ri]>arr[largest]) {
largest=ri;
}
if(largest!=i) {
int temp=arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
heapify(arr,n,largest);
}
}
void printArray(int[]arr) {
for(int i=0;i<arr.length;i++) {
System.out.println(arr[i]);
}
}
}