让heapsort以升序打印

import java.lang.*;
import java.util.*;

public class heap {

/*
 * Definitions of the parameters
 *    1) tree: the array where the sweeping window is implemented
 *    2) newEle: the new element to insert
 *    3) pos: where to insert the new element initially.
 *            note it does not mean newEle is going to
 *            stay at pos after this function
 *    4) increment
 *      a) true: insert newEle, that is all
 *      b) false: insert newEle and then remove the root
 */
static void insertHeapTreeAt(int[] tree, int newEle,
        int pos, boolean increment) {
    int temp;


    //place first element in, no need to start tree yet
    if (tree[0] == 0) {
        tree[0] = newEle;
    }

    //increment is true, sliding window isn't full yet
    if (increment == true) {
        tree[pos] = newEle;
        //create tree
        createTree(tree);

    } else {
        //increment is false, if larger than root do nothing
        //place in pos (being k+1), then swap with root.
        //then createTree slides everything so father > son

        if (newEle < tree[0]) {
            tree[pos] = newEle;
            temp = tree[0];
            tree[0] = tree[pos];
            tree[pos] = 0;
            createTree(tree);
        }
    }

    //Then need to compare the root down the tree to check for father>=son
}

static void createTree(int[] tree) {
    int i, father, son;

    for (i = 1; i < tree.length; i++) {
        int leaf = tree[i];
        son = i;
        father = (son - 1) / 2;

        while (son > 0 && tree[father] < tree[son]) {
            tree[son] = tree[father];
            tree[father] = leaf;
            son = father;
            father = (son - 1) / 2;
        }
    }

   // sort(tree);

}

static void sort(int[] tree) {
    int father, larger, temp;
    //father = 0;

    for (int i = tree.length - 1; i > 0; i--) {

        //No need to bubble down bc only 1 node
        if (i - 1 == 0) {
            break;
        }

        //two nodes, root and son
        if (i - 1 == 1) {
            //then the larger son has to be left (index = 1)
            larger = 1;
        } else {
            //compare left/right sons for larger
            larger = (tree[1] > tree[2]) ? 1 : 2;
        }

        //bubble down from root
        father = 0;
        while (tree[father] < tree[larger]) {
            temp = tree[father];
            tree[father] = tree[larger];
            tree[larger] = temp;

            father = larger;

            if (2 * father + 1 > i - 1) {
                break; //no son, rofl
            } else if (2 * father + 1 > i - 1) {
                larger = 2 * father + 1; //only left son
            } else {
                larger = (tree[2 * father + 2] > tree[2 * father + 1]) ? 2 * father + 2
                        : 2 * father + 1;

            }

        }
    }
}


static void sortAscending(int[] x){
    int father, son, temp;

    for (int i = 0; i < x.length-1; i++) {
        son = i;
        father = (son - 1) / 2;

        //while (son > 0 && x[father] > x[son]) {
        while(x[father] > x[son]){
            temp = x[son];
            x[son] = x[father];
            x[father] = temp;

            son = father;
            father = (son - 1) / 2;
        }
    }



}

/*
 * get the smallest k elements in array x in O(nlogn) time, where
 * n is the size of array x.
 *
 * It is supposed to return an array, containing the smallest k elements
 * in the increasing order.
 */
static int[] getSmallestK(int x[], int k) {

    if (k > x.length) {
        return null;
    }
    int[] result = new int[k + 1];

    // use the first k elements in x to construct an
    // almost complete binary tree, where father>=sons
    result[0] = x[0];
    for (int i = 1; i < k; i++) {
        insertHeapTreeAt(result, x[i], i, true);
    }

    // for each element in the rest of array x,
    // insert it in the almost complete binary tree, and then
    // remove the root in the tree.
    for (int i = k; i < x.length; i++) {
        insertHeapTreeAt(result, x[i], k, false);
    }

    // now the first k elements in result are the smallest k elements in x

    // sort the first k elements in result in O(klogk) time
    sortAscending(result);
    //sort(result);



    return result;
}

public static void main(String[] args) {


    // Basic Testing


    int[] data = {31, 44, 64, 5, 61,
        43, 6, 88, 59, 90,
        39, 97, 77, 62, 99,
        34, 57, 53, 60, 29};

    int[] smallestK = getSmallestK(data, 5);
    for (int i = 0; i < 5; i++) {
        System.out.print(smallestK[i] + ",");
    }
    System.out.println();


    // More Complete Testing

    Random random = new Random();
    List<Integer> numsList = new ArrayList<Integer>();
    int[] numsArray = new int[1000];
    for (int i = 0; i < 1000; i++) {
        int rand = 0;

        do {
            rand = random.nextInt(1000);
        } while (numsList.contains(rand));

        numsList.add(rand);
        numsArray[i] = rand;
    }

    Collections.sort(numsList);
    int[] smallest100 = getSmallestK(numsArray, 100);

    for (int i = 0; i < 100; i++) {
        System.out.print(smallest100[i] + ",");
    }
    System.out.println();

    for (int i = 0; i < 100; i++) {
        System.out.print(numsList.get(i) + ",");
    }

    for (int i = 0; i < 100; i++) {
        if (numsList.get(i) != smallest100[i]) {
            throw new RuntimeException("Error");
        }
    }

}