小顶堆排序Java代码样例

小顶堆排序Java代码样例

 

import java.util.Arrays;

public class MinHeapTopN {

    //    top num
    private int topN;
    //    top n number array
    private int[] topNHeap;

    /**
     * init
     *
     * @param topN
     * @param unSortedArray
     */
    public MinHeapTopN(int topN, int[] unSortedArray) {
        this.topN = topN;
        this.topNHeap = new int[topN];

//        init topN array
        for (int i = 0; i < topN; i++) {
            this.topNHeap[i] = unSortedArray[i];
        }

//        create min heap
        createMinHeap();

//        add new num
        for (int i = topN; i < unSortedArray.length; i++) {
            putNewNum(unSortedArray[i]);
        }
    }

    /**
     * put a new number to the min heap
     *
     * @param newNum
     */
    private void putNewNum(int newNum) {
//        only great than root node need to sort
        if (newNum > this.topNHeap[0]) {
            this.topNHeap[0] = newNum;
//                adjust heap
            UpToDown(0);
        }
    }

    /**
     * create a min heap
     */
    private void createMinHeap() {
//        the first no leaf node from the tail
        int pos = this.topN / 2;
        for (int i = pos; i >= 0; i--)
            UpToDown(i);
    }

    /**
     * adjust the heap
     *
     * @param i
     */
    private void UpToDown(int i) {
        int leftChildIndex, rightChildIndex, tmp, pos;
//       the left child index
        leftChildIndex = 2 * i + 1;
//        the right child index
        rightChildIndex = leftChildIndex + 1;

        if (leftChildIndex > (this.topN - 1)) {
//            no child
            return;
        } else {
            if (rightChildIndex > (this.topN - 1))
//                only have left child
                pos = leftChildIndex;
            else
//                get the index of great one
                pos = this.topNHeap[leftChildIndex] > this.topNHeap[rightChildIndex] ? rightChildIndex : leftChildIndex;

            if (this.topNHeap[i] > this.topNHeap[pos]) {
//                swap
                tmp = this.topNHeap[i];
                this.topNHeap[i] = this.topNHeap[pos];
                this.topNHeap[pos] = tmp;
//                continue adjust
                UpToDown(pos);
            }
        }
    }

    public static void main(String[] args) {
        int[] all = {16, 7, 3, 20, 17, 5698, 13, 120, 117, 318, 5213, 2120, 2117, 218};
        MinHeapTopN mntn = new MinHeapTopN(3, all);

        System.out.print(Arrays.toString(mntn.topNHeap));
    }
}