/** * Created by elvalad on 2014/12/8. * 输入N个整数，输出最小的K个 */import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;public class MinKArray {    /* 用二叉树表示一个堆 */    private class Heap {        private Node root;        private class Node {            int key;            Node left;            Node right;            Node(int key) {                this.key = key;            }        }        /* 建立最大堆，将元素插入到堆的合适位置 */        public void put(int key) {            root = put(root, key);        }        private Node put(Node x, int key) {            if (x == null)                return new Node(key);            int cmp = key - x.key;            if (cmp > 0) {                int tmp = x.key;                x.key = key;                key = tmp;                x.right = put(x.right, key);            } else if (cmp < 0) {                x.left = put(x.left, key);            }            return x;        }        public void deleteMax() {            root = deleteMax(root);        }        private Node deleteMax(Node x) {            if (x == null)                return null;            if ((x.left == null) && (x.right != null)) {                int tmp = x.key;                x.right.key = x.key;                x.key = tmp;                x.right = deleteMax(x.right);            } else if ((x.right == null) && (x.left != null)) {                int tmp = x.key;                x.left.key = x.key;                x.key = tmp;                x.left = deleteMax(x.left);            } else if ((x.left == null) && (x.right == null)) {                x = null;            } else {                int cmp = x.left.key - x.right.key;                if (cmp >= 0) {                    int tmp = x.key;                    x.key = x.left.key;                    x.left.key = tmp;                    x.left = deleteMax(x.left);                } else {                    int tmp = x.key;                    x.key = x.right.key;                    x.right.key = tmp;                    x.right = deleteMax(x.right);                }            }            return x;        }        public void printHeap(Node x) {            if (x == null)                return;            System.out.println(x.key);            printHeap(x.left);            printHeap(x.right);        }    }    /* 使用一般的排序算法，然后顺序输出前K个元素 */    public int[] minKArray1(int[] a, int k) {        Arrays.sort(a);        for (int i = 0; i < k; i++) {            System.out.println(a[i]);        }        return Arrays.copyOfRange(a, 0, k);    }    /* O(n)算法实现快速选择算法 */    public int[] minKArray2(int[] a, int k) {        return a;    }    /* 维护一个容量为K的最大堆，《算法导论》第6章堆排序 */    public int[] minKArray3(int[] a, int k) {        Heap h = new Heap();        for (int i = 0; i < k; i++) {            h.put(a[i]);        }        for (int i = k; i < a.length; i++) {            if (a[i] >= h.root.key) {                continue;            } else {                h.put(a[i]);                h.deleteMax();            }        }        h.printHeap(h.root);        return a;    }    public static void main(String[] args) {        Scanner scan = new Scanner(System.in);        ArrayList<Integer> array = new ArrayList<Integer>();        while (scan.hasNext()) {            array.add(scan.nextInt());        }        int[] a = new int[array.size()];        for (int i = 0; i < a.length; i++) {            a[i] = array.get(i);        }        MinKArray mka = new MinKArray();        mka.minKArray1(a, 8);        System.out.println("---------------");        mka.minKArray3(a, 8);    }}