package kopiec;

	public class Heap {

		int left;
		int right;
		int heap[];
		int n;
		int smaller;

	public Heap(int size){
		heap = new int[size];
	}

	public void buildingHeap(int[] heap){
		n = heap.length-2;
		for(int i =n/2; i>=0;i--){
			findMinimum(i);
		}
	}

	public void findMinimum(int i){
		left = 2*i+1;
		right = 2*i+2;
		if (left<= n && heap[left] < heap[i])
			smaller = left;
		else
			smaller = i;
		if (right <= n && heap[right] < heap[i])
			if(heap[smaller]>heap[right])
				smaller = right;
		if (smaller != i){
			swap(i,smaller);
			findMinimum(smaller);
		}
	}

	public void swap(int i, int j){
		int tmp = heap[i];
		heap[i] = heap[j];
		heap[j] = tmp;
	}

	public void heapSort(int [] tab){
		heap=tab;
		buildingHeap(heap);
		for(int i=n+1;i>0;i--)		{
			swap(0,i);
			n=n-1;
			findMinimum(0);
		}
	}

	public void insert(int value){
		int i=0;
		if(heap.length==0)
			heap=biggerHeap();
		heap=biggerHeap();
		i=heap.length-1;
		heap[i]=value;

		while(heap[(i-1)/2]>heap[i]){
			int x=heap[(i-1)/2];
			heap[(i-1)/2]=heap[i];
			heap[i]=x;
			i=(i-1)/2;
		}
	}

	private int []biggerHeap(){
		int []heap1=new int[heap.length+1];
		System.arraycopy(heap,0,heap1,0,heap.length);
		return heap1;
	}

	public void heapDisplay(){
		for(int i=0;i<heap.length;i++)
			System.out.print(heap[i]+", ");
		System.out.println();
	}



}