Функция вставки в maxHeap имеет нежелательное поведение

Question

имеет функцию вставки, которая должна вставлять элемент в кучу.

public void insert(int element) {
    Heap[++this.size] = element;
    int i = this.size;
    while (Heap[i] > Heap[parent(i)]) {
        swap(i, parent(i));
        i = parent(i);
    }
    for (int j = 0; j < size; j++)
        System.out.println(Heap[j]);
    System.out.println();
}

Цикл for с операторами print предназначен для вывода образца, я вернусь к этому.parent (i) получает i / 2, а size - это текущий размер кучи.

И это функция подкачки:

private void swap(int first, int second) {
    int buffer = Heap[first];
    Heap[first] = Heap[second];
    Heap[second] = buffer;
}

Введенные мной примеры элементов: 950, 800,850, 900, 850, 1000. Цикл for в Insert () предназначен для отображения значений в том виде, в котором я их поместил (с новой строкой между каждой вставкой).

Я не понимаю, почему значение 800 устанавливается на 0. Затем оно восстанавливается как 800, но после этого устанавливается на 0.Какая часть моего кода дает ему эту функциональность?

Answer 1

Проблема в вашем методе insert прямо здесь:

Heap[++this.size] = element;
int i = this.size;

Итак, когда вы в первый раз вызываете insert, ваш массив выглядит так:

Heap[0] = 0
Heap[1] = 950

this.size равно 1, и вы начинаете отсеивать кучу с индекса 1.

Это может закончиться только плохо.После второй вставки ваш массив содержит [950,800], а this.size равен 2. Теперь давайте посмотрим, что произойдет с третьей вставкой, когда вы вставите 850.

Heap[++this.size] = 850

Итак this.sizeувеличивается на 3, значение 850 вставляется в Heap[3], давая вам [900, 800, 0, 850].Это соответствует этой куче:

        900
       /   \
     800    0
    /
  850

Ваш код корректно переставляет кучу, давая вам:

        900
       /   \
     850    0
    /
  800

Что соответствует массиву [900, 850, 0, 800].

проблема в том, что вы увеличиваете размер до вставки элемента.Вам нужно увеличить после вставки .И затем, поскольку он основан на 0, вы хотите, чтобы начальный индекс был size-1.

Вот исправленный метод.

public void insert(int element) {
    Heap[this.size++] = element;
    int i = this.size-1;

    while (i > 0 && Heap[i] > Heap[parent(i)]) {
        swap(i, parent(i));
        i = parent(i);
    }
    for (int j = 0; j < size; j++)
        System.out.println(Heap[j]);
    System.out.println();
}

Кстати, в куче на основе 0родительский элемент узла i должен быть (i-1)/2.