import java.io.*;

class sort {
	int list[];

	/* Constructor of the class */
	sort(int ... array) {
		list = array;
		sorttree();
		System.out.println("After sort array in Binary Tree format:");
		display();
		heap();
		System.out.println("Sorted array:");
		display();
	}
										
	void sorttree() {
		int root, c;
		for(int i = 1; i < list.length; i++) {
			c = i;
			do {
				root = (c - 1) / 2;
				if(list[root] < list[c])
					swap(root, c);
				c = root;
			}
			while(c != 0);
		}
	}
										
	void heap() {
		for(int j = list.length - 1; j >= 0; j--) {
			swap(0, j);
			int c = 0, root = 0;
			do {
				c = 2 * root + 1;
				if(c < list.length-1) {
					if(list[c] < list[c+1] && c < (j-1))
						c++;
					if(list[root] < list[c] && c < j)
						swap(root, c);
					root = c;
				}
			}
			while(c < j);
		}
	}
										
	void swap(int i, int j) {
		int temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}
										
	void display() {
		for(int k:list)
			System.out.println(k);
	}
}
										
class heapsort {
	public static void main(String args[ ]) {
		new sort(6,2,4,1,3,0,5,8,7,9);
	}
}


          /****** Output ******/
          
After sort array in Binary Tree format:

9

8

5

6

7

0

4

1

3

2

Sorted array:

0

1

2

3

4

5

6

7

8

9