public class MinHeap {

    /*

     *

     * Top K个问题，求给定数据中最小的K个数

     *

     * 最小堆解决：堆顶元素为堆中最大元素

     *

     *

     *

     */

    private int MAX_DATA = 10;//最小10个数

    private int[] data;//存储数据

    private int len;//当前存储长度，考虑到元素个数可能没有10个，这个时候全部输出

    private MinHeap() {

        data = new int[MAX_DATA];

        len=0;

    }

    private MinHeap(int max) {

        this.MAX_DATA = max;

        data = new int[MAX_DATA];

        len=0;

    }

    public void setRoot(int root) {

        this.data[0] = root;

    }

    public void addData(int da) {

        if (this.len < this.MAX_DATA)

        {

            this.data[this.len] = da;

            len++;

            if(len==this.MAX_DATA)

                this.adjust(0);

        }

        else if(da<this.getRoot())

        {

            this.setRoot(da);

            this.adjust(0);

        }

    }

    private void adjust(int index)

    {

        int left=index*2+1;

        int right=index*2+2;

        if(left<this.len&&right<(this.len)&&data[index]>=data[left]&&data[index]>=data[right])

            return;

        if(left<this.len&&data[index]<data[left])

        {

            data[index]^=data[left];//两个数交换

            data[left]^=data[index];

            data[index]^=data[left];

            this.adjust(left);

        }

        if(right<(this.len)&&data[index]<data[right])

        {

            data[index]^=data[right];

            data[right]^=data[index];

            data[index]^=data[right];

            this.adjust(right);

        }

    }

    private int getRoot()

    {

        return this.data[0];

    }

    public String toString()

    {

        for(int i=0;i<this.len;i++)

            System.out.print(data[i]+"/");

        return null;

    }

    public static void main(String args[])

    {

        MinHeap min=new MinHeap();

        for(int i=200;i>0;i--)

        {

            min.addData(i);

            min.toString();

            System.out.print("\n");

        }

    }

}