Максимальная загрузка и сортировка кучи Java - PullRequest
Новая
       41

Максимальная загрузка и сортировка кучи Java

0 голосов
/ 03 марта 2020

Я пытаюсь создать максимальную кучу, и когда каждое новое значение вставляется, значение сдвигается вверх или вниз в правильное положение, мне еще предстоит реализовать функцию сдвига вниз, так что на данный момент я использую тест это должно только потребовать, чтобы программа сдвинулась вверх. Данные теста вводятся в следующем порядке:

[16, 10, 14, 9, 7, 1, 4, 2, 8, 3]

Я использую следующий код в главном классе для вставки значений в кучу: 

package com.company;

public class Main {

    public static void main(String[] args) {

        BinaryHeap bh = new BinaryHeap();

        bh.insert(16);
        bh.insert(10);
        bh.insert(14);
        bh.insert(9);
        bh.insert(7);
        bh.insert(1);
        bh.insert(4);
        bh.insert(2);
        bh.insert(8);
        bh.insert(3);

        bh.printHeap();

    }
}

И этот следующий бит кода, где происходит вставка и сдвиг: 

package com.company;

public class BinaryHeap {
    private int[] Heap;
    private int size;
    private int maxsize;

    public BinaryHeap(){
        this.maxsize = 10;
        this.size = 0;
        Heap = new int[this.maxsize + 1];
    }

    public int Parent(int i){

        return (i)/2;
    }

    public int LeftChild(int i){

        return (2*i);
    }

    public int RightChild(int i){

        return ((2*1)+1);
    }

    public void insert(int value) {
        if(size <= Heap.length) {
            size++;
            Heap[size] = value;
            siftUp(size);
        }
    }


    private void siftUp(int i) {
        int parentIndex;
        int tmp;

        if (i != 0) {

            parentIndex = Parent(i);

            if (Heap[parentIndex] < Heap[i]) {
                tmp = Heap[parentIndex];
                Heap[parentIndex] = Heap[i];
                Heap[i] = tmp;
                siftUp(parentIndex);
            }

        }

    }

    public void printHeap()
    {
        for (int i = 1; i < maxsize; i++) {
            System.out.print(" PARENT : " + Heap[Parent(i)]
                    + " LEFT CHILD : " + Heap[LeftChild(i)]
                    + " RIGHT CHILD :" + Heap[RightChild(i)]);
            System.out.println();
        }
    }

}

Функция сдвига siftUp (), который я считаю проблемой. Когда программа запускается со следующими выходными данными: 

PARENT : 16 LEFT CHILD : 9 RIGHT CHILD :10
 PARENT : 14 LEFT CHILD : 8 RIGHT CHILD :10
 PARENT : 14 LEFT CHILD : 1 RIGHT CHILD :10
 PARENT : 9 LEFT CHILD : 0 RIGHT CHILD :10
 PARENT : 9 LEFT CHILD : 3 RIGHT CHILD :10
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 12 out of bounds for length 11
    at com.company.BinaryHeap.printHeap(BinaryHeap.java:61)
    at com.company.Main.main(Main.java:20)

Но это не правильно, потому что 1) исключение индекса вне границ в конце, которое приходит из функции printHeap () и 2) дочерние элементы каждого родительского узла не в нужном месте, потому что узел root должен быть 16 с 14 и 10 как дочерние, также, когда он печатает значения для кучи, он печатает 0, однако 0 никогда не вставляется в куча. Я попытался выполнить некоторые из моих собственных отладок, но без особого успеха, поэтому любая помощь в этом приветствуется.

1 Ответ

1 голос
/ 03 марта 2020 
private void siftUp(int i) {
    int parentIndex;
    int tmp;
    if (i != 0) { // error is this if statement
        parentIndex = Parent(i);
        if (Heap[parentIndex] < Heap[i]) {
            tmp = Heap[parentIndex];
            Heap[parentIndex] = Heap[i];
            Heap[i] = tmp;
            siftUp(parentIndex);
        }
    }
}

Ошибка, из-за которой ваша куча не отображает правильное число, находится внутри siftUp, оператора if.

Когда вы вставляете 16, Heap[1] становится 16. Затем он вызывает siftUp(1). Внутри siftUp 1! = 0, поэтому операторы if выполняются. parentIndex становится 1/2 = 0, и здесь возникает проблема. Heap [0] = 0 по умолчанию меньше Heap [1] = 16. Таким образом, он меняет значения 16 и 0, перемещая 16 в индекс 0, который не является заголовком, как вы упомянули. Это только начало ошибок, и когда вы вставляете все больше и больше чисел, они становятся повсеместными.

Поскольку ваш root кучи находится в индексе 1. Вы должны просеивать только до индекса 1, который не имеет родителя. После изменения оператора if на if(i > 1) и изменения вашего printHeap () я получаю этот вывод, который я считаю правильным. Вы также должны напечатать текущее значение по текущему индексу в куче. 

 PARENT: 0 CURRENT: 16 LEFT CHILD : 10 RIGHT CHILD : 14 
 PARENT: 16 CURRENT: 10 LEFT CHILD : 9 RIGHT CHILD : 7
 PARENT: 16 CURRENT: 14 LEFT CHILD : 1 RIGHT CHILD : 4
 PARENT: 10 CURRENT: 9 LEFT CHILD : 2 RIGHT CHILD : 8
 PARENT: 10 CURRENT: 7 LEFT CHILD : 3
 PARENT: 14 CURRENT: 1
 PARENT: 14 CURRENT: 4
 PARENT: 9 CURRENT: 2
 PARENT: 9 CURRENT: 8

public void printHeap(){
  for (int i = 1; i < maxsize; i++) {
    System.out.print(" PARENT: " + Heap[Parent(i)]);
    System.out.print(" CURRENT: "+ Heap[i]);
    if(LeftChild(i) <=  10){
      System.out.print(" LEFT CHILD " + ": " +  Heap[LeftChild(i)]);
    } 
    if(RightChild(i) <= 10){
      System.out.print(" RIGHT CHILD "+ ": "+  Heap[RightChild(i)]);
      }
    System.out.println();
  }
}
...