Сортировка кучи не работает?

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 не дает мне родителя, как это должно быть?

Answer 1

Вот необходимые проверки в downHeap:

1. Местоположение должно быть в пределах размера кучи
2. Правильный ли дочерний элемент в пределах размера кучи И правильныйпотомок меньше левого потомка и родитель

3. В противном случае, левый потомок в пределах размера кучи И левый потомок меньше, чем родитель

   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 () вы должны скопировать значение min перед его перезаписью:

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