Learn Java Java Tutoring is a resource blog on java focused mostly on beginners to learn Java in the simplest way without much effort you can access unlimited programs, interview questions, examples
Implement Heap sort using Java – We will discuss about the methods to Implement heapsort in Java. Compiler has been added so that you can easily execute the programs on your own, alongside suitable examples and sample outputs. The methods are as follows:
- Using Array.
- Using Buffered Reader.
HeapSort Java Program – Using Array
1) Using Scanner class method nextInt(), read the entered numbers and store the numbers in to the array a[].
2) In the heap tree every parent node should not contain greater child node, so we should build the complete ordered tree using bheap() method.
3) First we have to ordered the rightmost tree, then leftmost tree.
4) The array elements are 5, 1, 0, 54, 2, 22, represents not ordered tree.
5) At height 1, 0 has the greater child 22 so move 0 to downward and place 22 in the position of 0. The leftmost tree 1 has the greater child 54 so move 1 to downward and place 54 in the position of 1.
Now the array is 5, 54, 22, 1, 2, 0. The 54 is the greater child of 5 in leftmost tree. So move 5 to downward and place 54 at the position of 5. Now the series is 54, 5, 22, 1, 2, 0.
6) Now sort the elements of tree using sort() method.
7) First delete the top element of the tree and place that element at last node of the tree. After delete and place the top element, again build a complete ordered tree with remaining elements. Repeat this until array is sorted completely.
From the complete ordered array elements delete 54 and place it at last index of the array, build the complete ordered tree.
Now the array is 22,5,0,1,2,54. Next delete 22 and place it at the proper position of the array and build the complete ordered tree. Now the array is 5,2,0,1,22,54.
Delete 5 and build complete ordered tree, the array is 2,1,0,5,22,54. Delete 2 and build the complete ordered tree, now the array is 1,0,2,5,22,54. Delete 1 and build the complete ordered tree. Now the sorted array is 0, 1, 2, 5, 22, 54.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
import java.util.Scanner; public class HSort { public static void heapify(int a[],int i,int n) { int l=2*i+1; int r=2*i+2; int temp,largest; if(l<n && a[l]>a[i]) largest=l; else largest=i; if(r<n && a[r]>a[largest]) largest=r; if(largest !=i) { temp=a[largest]; a[largest]=a[i]; a[i]=temp; heapify(a,largest,n); } } public static void bheap(int a[]) { for(int i=(a.length/2)-1;i>=0;i--) { heapify(a,i,a.length); } } public static void Sort(int a[]) { int temp,j,i; bheap(a); for( i=(a.length)-1; i>0;) { temp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,0,i--) ; } } public static void printarray(int a[]) { System.out.println(); for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) { int n, res,i; Scanner s = new Scanner(System.in); System.out.print("Enter number of elements in the array:"); n = s.nextInt(); int a[] = new int[n]; System.out.println("Enter "+n+" elements "); for( i=0; i < n; i++) { a[i] = s.nextInt(); } System.out.println( "elements in array "); printarray(a); Sort(a); System.out.println( "\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Enter number of elements in the array:6 Enter 6 elements 5 1 0 54 2 22 elements in array 5 1 0 54 2 22 elements after sorting 0 1 2 5 22 54 |
Heap Sort – Using Buffered Reader
1) Buffered Reader class reads the data as string from character input stream and it throws IO Exception.
2) bheap() mathod builds a complete ordered tree, sort() method sort the elements of complete ordered tree array elements.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import java.io.*; public class HSort { public static void heapify(int a[],int i,int n) { int l=2*i+1; int r=2*i+2; int temp,largest; if(l<n && a[l]>a[i]) largest=l; else largest=i; if(r<n && a[r]>a[largest]) largest=r; if(largest !=i) { temp=a[largest]; a[largest]=a[i]; a[i]=temp; heapify(a,largest,n); } } public static void bheap(int a[]) { for(int i=(a.length/2)-1;i>=0;i--) { heapify(a,i,a.length); } } public static void Sort(int a[]) { int temp,j,i; bheap(a); for( i=(a.length)-1; i>0;) { temp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,0,i--) ; } } public static void printarray(int a[]) { System.out.println(); for(int i=0; i < a.length; i++) { System.out.print(a[i]+" "); } } public static void main(String[] args) throws IOException { int n,i; BufferedReader b=new BufferedReader(new InputStreamReader(System.in)); System.out.println("enter N: "); n=Integer.parseInt(b.readLine()); int a[] = new int[n]; System.out.println("enter "+n+" elements "); for(i= 0; i< n; i++) a[i] = Integer.parseInt(b.readLine()); System.out.println("elements in array "); printarray(a); Sort(a); System.out.println("\nelements after sorting"); printarray(a); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Enter number of elements in the array:6 Enter 6 elements 5 1 0 54 2 22 elements in array 5 1 0 54 2 22 elements after sorting 0 1 2 5 22 54 |
If you have any doubts or suggestions related to implement Heap sort Java program, leave a comment here.
More Programs:
