package com.company;

/**
 * Created by zqiguo on 2017/3/11.
 */
public class Heap {
    private int heapSize;
    private int currentSize;
    private int[] heapArray;

    /**
     * siftDown algorithm when build a heap from an array
     * if you know the storage of a complete binary tree well, it‘s easy.
     * The point is how to reduce the move of array element.
     * @param pos int,  the position to start siftDown
     */
    private void siftDown(int pos){
        int tmp = heapArray[pos];
        while (pos * 2 + 1 < currentSize){
            int minIndex = pos * 2 + 1;
            if (minIndex + 1 < currentSize){
                minIndex = heapArray[minIndex] <= heapArray[minIndex+1] ? minIndex : minIndex+1;
            }
            if (heapArray[minIndex] < tmp){
                heapArray[pos] = heapArray[minIndex];
                pos = minIndex;
            }else {
                break;
            }
        }
        heapArray[pos] = tmp;
    }

    /**
     * return the top of the heap
     * @return the top of the heap
     */
    public int getTop(){
        return heapArray[0];
    }

    public void printHeap(){
        for (int i = 0; i < currentSize; i++)
        {
            System.out.printf(heapArray[i] + " ");
        }
        System.out.println();
    }
    public Heap(){
        heapSize = 5;
        currentSize = 0;
        heapArray = new int[heapSize];
    }

    /**
     * build a heap from an array.
     * @param array
     */
    public Heap(int[] array){
        currentSize = array.length;
        if (heapSize < currentSize){
            heapArray = new int[currentSize];
            heapSize = currentSize;
        }
        for (int i = 0; i < currentSize; i++) {
            heapArray[i] = array[i];
        }
        int lastParent = (currentSize - 2) / 2;
        while (lastParent >= 0){
            siftDown(lastParent--);
        }
    }

    /**
     * insert an element to heap. auto resize the heapArray, if full.
     * @param element
     * @return
     */
    public boolean insert(int element){
        if (currentSize == heapSize){
            int[] tmp = new int[heapSize*2];
            for (int i = 0; i < currentSize; i++) {
                tmp[i] = heapArray[i];
            }
            heapArray = tmp;
            heapSize = tmp.length;
        }
        heapArray[currentSize] = element;
        siftUp(currentSize);
        currentSize++;
        return true;
    }

    /**
     * delete the top of the heap
     * @return the top of heap
     */
    public int delete(){
        if (currentSize == 0){
            System.out.println("The heap is empty!");
            return -1;
        }else {
            int tmp = heapArray[0];
            heapArray[0] = heapArray[currentSize-1];
            currentSize--;
            siftDown(0);
            return tmp;
        }
    }

    /**
     * siftup adjust, used by insert.
     * @param start
     */
    private void siftUp(int start){
        int tmp = heapArray[start];
        while (start > 0){
            int parentIndex = (start-1) / 2;
            if (heapArray[parentIndex] > tmp){
                heapArray[start] = heapArray[parentIndex];
                start = parentIndex;
            }else {
                break;
            }
        }
        heapArray[start] = tmp;
    }

    public static  void main(String[] args){
        int [] array = new int[]{7,6,5,4,3,2,1};
        Heap heap = new Heap(array);
        heap.printHeap();
        heap.insert(0);
        heap.printHeap();
        heap.delete();
        heap.printHeap();
    }
}