import java.io.*;
import java.util.*;
class heapSort
   {
   	public static void main(String[] args)
      	{
      		int n = 40;
		int[] list = new int[n];
		Random rand = new Random();
		
		System.out.println("Input array: ");
		for(int i = 0; i < n; i++)	
		{
			list[i] = rand.nextInt(n);
			System.out.print(list[i]+" ");
		}
		System.out.println(" ");
		
      		Heap theHeap = new Heap(n);  

		// Build a heap with elements from list
		for(int i = 0; i < n; i++)
		{
			Node newNode = new Node(list[i]);
			theHeap.insert(newNode);
		}

		// Extract elements from the heap, one at a time
		// and insert these in the appropriate places in the array
		for(int i = 0; i < n; i++)
		{
			Node newNode = theHeap.delete();
			list[n-i-1] = newNode.getPriority();
		}

		// Print sorted array
		System.out.println("Sorted array: ");
		for(int i = 0; i < n; i++)	
			System.out.print(list[i]+" ");
		System.out.println(" ");

      }  // end main()
} // end of class heapSort
////////////////////////////////////////////////////////////////