与えられたデータの中で最小のK個の数を求めます

6601 ワード

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("
"); } } }