forked from hussien89aa/DataStructureAndAlgorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHeapSort.java
More file actions
45 lines (42 loc) · 936 Bytes
/
HeapSort.java
File metadata and controls
45 lines (42 loc) · 936 Bytes
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
package com.sort;
public class HeapSort {
static int total;
static void swap(Comparable[] arr, int a, int b){
Comparable temp= arr[a];
arr[a]= arr[b];
arr[b]= temp;
}
static void heapify(Comparable[] arr, int i){
int lft= i*2;
int rgt=i*2+1;
int grt=i;
if( lft<= total && arr[lft].compareTo(arr[grt])>=0)
grt=lft;
if( rgt<= total && arr[rgt].compareTo(arr[grt])>=0)
grt=rgt;
if( grt!=i){
swap(arr,i,grt);
heapify(arr, grt);
}
}
static void sort( Comparable[] arr){
total=arr.length-1;
for(int i=total/2;i>=0;i--)
heapify(arr, i);
for(int i=total;i>0;i--){
swap(arr,0,i);
total--;
heapify(arr, 0);
}
}
public static void main(String[] args) {
Integer[] arr={1,50,30,10,60,80};
System.out.println("Before Sort");
for(int i=0;i<arr.length;i++)
System.out.print(arr[i] +"\t");
sort(arr);
System.out.println("\nAfter Sort");
for(int i=0;i<arr.length;i++)
System.out.print(arr[i] +"\t");
}
}