获取堆排序以升序打印

Question

该程序采用一个长度为 n 的数组，并使用堆排序来取出最小的 k 个元素。我已经从数组中取出了 k 个最小元素，但我已经尝试了几个小时才能让它们按升序打印。几乎完整的二叉树正在正确构建，基于father > 。儿子。如果有人可以帮助我弄清楚我需要做什么，我将不胜感激。

另外，这是一项家庭作业，我并不是要求代码来修复它。我确实被难住了，只想设置在正确的路径上以使其正常工作。预先感谢您的任何意见。

编辑-我有点让它按升序输出，对于我目前正在进行的基本测试： 5,6,31,34,29,

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

}

}

Answer 1

传递 比较器< /a> 到实现堆的函数。要更改排序顺序，请传递不同的Comparator。

static void sortAscending(int[] x, Comparator comp){

然后

    while(comp.compare(x[father], x[son]) > 0){

等等

Answer 2

public class MaxHeap {

    private int size;
    private int arr[] ;

    MaxHeap(int a[], int size){
        this.size= size;
         arr = a;   
    }

     public void buildHeap(){

         for (int i = (size -2)/2 ;i>=0;i--)
         {
             heapify(i);

         }

     }

     public void heapify(int idx){

        int left = 2*idx+1;
        int right= 2*idx+2;
        int largest= idx;

        if(left < size && arr[left] > arr[largest])
        {
            largest = left;
        }

        if(right < size && arr[right] > arr[largest])
        {
            largest = right;
        }
        if(largest!=idx){
        swap(idx,largest);
        heapify(largest);
        }

     }

    public void sort(){

        buildHeap();

        while(size > 1)
        {
            swap(0,size-1);
            size--;
            heapify(0);


        }
    }

    public void swap(int i, int j){
        int k = arr[i];
        arr[i]=arr[j];
        arr[j]=k;
    }


    public void print(int k){
    for(int i=0;i<k;i++){
        System.out.println(arr[i]);
        }
    }
    public static void main(String args[]){

        int array[]={10,12,9,14,27,4,50};
        int k = array.length;

        MaxHeap mh = new MaxHeap(array,k);
        mh.sort();

        mh.print(k);

    }

}