java - 堆排序堆方法不起作用？

Question

一段时间以来，我真的一直在纠结这个问题，我真的愿意为这个问题的一些答案而死。

我有一个基于数组的堆实现。我的向上堆排序似乎在工作，但是当我弹出最高值时，我无法让向下堆排序工作。我已经将完整的代码放在一起，如果有人可以更正 downHeap 方法以便它能够在删除最高值时对该数组进行排序，我会很高兴:

public class HeapSortArray {
static int sizeOfTree = 0; 

    private static int arrayBufferSize = 50;

    public static int[] heap = new int[arrayBufferSize];
    static int[] numbers = new int[]{ 0, 7, 9, 7, 5, 2, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };


    public static void main(String[] args) {
        insert(0);  //set 0 of the array to nothing

        //fill array with numbers
        for (int i = 1; i < numbers.length; i++) {

            insert(numbers[i]);
          if (i > 1) {
            upHeap(i);
          }
        }
        System.out.println("Heap Printed once inserted: ");
        for(int i=1; i < numbers.length; i++){
            System.out.println(heap[i]);
        }
        System.out.println("----------------------");
        System.out.println("Heap Printed as top value is popped out: ");
        //pop lowest value 
        for(int i = numbers.length; i != 1; i--){
             removeMin();
            }

    }




    public static void upHeap(int childLocation) {      

        int parentLocation = childLocation / 2;
        int child = childLocation;
        int parentTemp = heap[parentLocation];
        int childTemp = heap[childLocation];

        int parentValue = heap[parentLocation];
        int childValue =  heap[child];

        if (parentValue > childValue) {
            heap[parentLocation] = childTemp;
            heap[childLocation] = parentTemp;
        }
        if (parentLocation != 1) {
            upHeap(parentLocation);
        }
      }


    public static void downHeap(int location){

        if(location > 0){


            int parentLocation = location;
            int leftchildLocation = 2*location;
            int rightchildLocation = 2*location+1;


            int parentValue = heap[parentLocation];
            int leftchildValue = heap[leftchildLocation];
            int rightchildValue = heap[rightchildLocation];


            int parentTemp = heap[parentLocation];
            int leftChildTemp = heap[leftchildLocation];
            int rightChildTemp = heap[rightchildLocation];

            if(leftchildValue < rightchildValue && leftchildValue < parentValue){
                heap[parentLocation] =  leftchildValue;
                heap[leftchildLocation] = parentTemp;
                downHeap(leftchildLocation);
            }

            if(rightchildValue < leftchildValue && rightchildValue < parentValue){
                heap[parentLocation] =  rightchildValue;
                heap[rightchildLocation] = parentTemp;
                downHeap(rightchildLocation);
            }

        }

    }

    public static int removeMin() {

        sizeOfTree--;

        if(sizeOfTree > 1){
        heap[1] = heap[sizeOfTree];

        downHeap(1);
        }
        int toReturn = heap[1];
        System.out.println(toReturn);

        return toReturn;
    }

    public static void insert(int toInsert) {

        heap[sizeOfTree] = toInsert;    


    if(sizeOfTree > 1){
            upHeap(sizeOfTree);
            }


            sizeOfTree++;

        }

}

非常感谢任何可以阐明这一点的人。

编辑:如果在第 38 行是这样的话，上面的实现将起作用:

int parentLocation = childLocation / 2;

更改为:

int parentLocation = childLocation -1;

我知道第二种方法不是它应该完成的方式，但为什么我的 childLocation/2 没有按应有的方式给我 parent ？

Answer 1

以下是 downHeap 中必要的检查:

1. 位置必须在堆的大小范围内
2. 右 child 是否在堆的大小之内并且右 child 是否小于左 child 和父

3. 否则，左 child 是否在堆的大小内并且左 child 是否小于父

   public static void downHeap(int location){
   if(location < sizeOfTree){
       int p = location;
       int l = 2*p;
       int r = 2*p+1;
       int s = sizeOfTree;
       if(r<s && heap[r]<heap[p] && heap[r]<heap[l]){
           int temp = heap[r];
           heap[r] = heap[p];
           heap[p] = temp;
           downHeap(r);
       }else if(l<s && heap[l]<heap[p]){
           int temp = heap[l];
           heap[l] = heap[p];
           heap[p] = temp;
           downHeap(l);
       }
   }}
   

同样在 removeMin() 中，您应该在覆盖之前复制最小值:

    public static int removeMin() {
    sizeOfTree--;
    int toReturn = heap[1];
    if(sizeOfTree > 1){
        heap[1] = heap[sizeOfTree];
        downHeap(1);
    }
    System.out.println(toReturn);
    return toReturn;
}