/**
	 * Given a node at index i in a heap this method let the node slide down
	 * the heap to its correct position by swapping relevant values. This method
	 * calls itself.
	 * 
	 * @param A The array that represents the heap.
	 * @param heapSize The size of the heap.
	 * @param i The index of the current node.
	 */
	private void maxHeapify( int[] A, int heapSize, int i )
	{
	
		//Aufgabe 9a)
		int l, r, largest;
		
		l = left(i);		
		r = right(i);
		
		comparisons++;
		if(l <= heapSize && A[l] > A[i]){
			largest = l;
		}else{
			largest = i;
		}
		
		comparisons++;
		if(r <= heapSize && A[r] > A[largest]){
			largest = r;
		}
			
		if(largest != i){
			swap(A, i, largest);
			maxHeapify(A, heapSize, largest);
		}
		
	}


	/**
	 * This method builds a max heap. In a max heap the root node has 
	 * the hightest value.
	 * 
	 * @param A The array that represents the heap.
	 */
	private void buildMaxHeap( int[] A )
	{
		//Aufgabe 9b)
		int i, heapSize;
		
		heapSize = A.length - 1;
		i = (int) (Math.ceil((A.length-1) / 2));		
		
		for(; i >= 0; i--){
			maxHeapify(A, heapSize, i);
		}
		
	}

	/**
	 * Sort the array A by performing heapsort.
	 */
	public void sort( int[] A )
	{
		//Aufgabe 9c)
		int i, heapSize;
		heapSize = A.length - 1;
		
		buildMaxHeap(A);
		
		for(i=A.length - 1; i > 0; i--){
			swap(A, 0, i);
			heapSize--;
			maxHeapify(A, heapSize, 0);
		}
	}