Binary вставки кучи, не понимают цикл

Question

в структурах данных Вайса и алгоритмы в Java», он объясняет алгоритм вставки для двоичных куч константы выглядит

public void insert(AnyType x) 
{ 
    if(currentSize == array.length -1) 
     enlargeArray(array.length * 2 + 1); 

    // Percolate up 
int hole = ++currentSize; 
for(array[0] = x; x.compareTo(array[ hole/2 ]) < 0; hole /=2) 
    array[ hole ] = array[ hole/2 ]; 
array[ hole ] = x; 
} 

Я получаю принцип перемещения отверстия вверх по дерево, но я не понимаю, как он справляется с этим синтаксисом в цикле for ... Что означает инициализатор array[0] = x;? Кажется, он перезаписывает значение root? Это похоже на очень надуманный кусок кода. ere?

Answer 1

Инициализатор массива выглядит неправильно. Если это массив [отверстие] = x ;, то вся вещь имеет смысл.

Сначала он помещает значение в нижний ранг дерева (запись после текущего размера), затем он смотрит в записи `над ним ', просматривая отверстие (int)/2.

Он продолжает перемещать его до тех пор, пока компаратор не начнет останавливаться. Я думаю, что это небольшое злоупотребление синтаксисом цикла for, так как он действительно похож на свое время (x.compare (hole/2) < 0) type loop.

Answer 2

Во-первых, я получил ответ от Марка Вайса и его письмо в основном сказал, что код правильный (полный ответ внизу этого ответа).

Он также сказал, что это:

Следовательно, минимальный элемент в индексе массива 1, как показано в findMin. Чтобы выполнить вставку, вы следуете по пути от корня до корня.

Индекс 1? Хм ... Мне тогда пришлось вернуться и перечитать большие части главы, и когда я увидел цифру 6.3, она нажала.

Массив основан на 0, но элементы, которые считаются частью кучи, сохраняются из индекса 1 и далее. Иллюстрация 6.3 выглядит следующим образом:

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
| | A | B | C | D | E | F | G | H | I | J | | | | 
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 

Размещение значения в элементе 0 представляет собой значение сторожевого сделать цикл завершается.

Таким образом, с приведенным выше деревом давайте посмотрим, как работает функция вставки. H ниже отмечает отверстие.

Сначала мы помещаем x в 0-й элемент (вне кучи) и размещаем отверстие в следующем доступном элементе массива.

           H 
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
| x | A | B | C | D | E | F | G | H | I | J | | | | 
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 

Тогда мы пузыриться (просачиваются) отверстие, перемещая значения по сравнению с «половиной индекса», пока мы не найдем правильное место, чтобы разместить x.

Если мы посмотрим на рисунке 6.5 и 6.6, давайте разместим фактические значения в массив:

      H/2       H 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | | | | 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 

Обратите внимание, что мы поместили 14, значение для вставки, в индекс 0, но это за пределами кучи , наше контрольное значение, чтобы обеспечить завершение цикла.

Затем мы сравниваем значение x со значением на hole/2, который теперь составляет 11/2 = 5.х меньше 31, поэтому мы перемещаем значение вверх и переместить отверстие:

  H/2    H <--------------------------- 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | 31 | | | 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 
          |       ^
          +--------- move 31 -----------+ 

Мы сравниваем раз, 14 раз меньше, чем 21 (5/2 = 2), так что еще раз:

 H/2 H <------------ 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
| 14 | 13 | 21 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 | | | 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 
      |   ^
      +-- move 21 ---+ 

Теперь, однако, 14 не менее 13 (отверстие/2 -> 2/1 = 1), так что мы нашли правильное место для x:

+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
| 14 | 13 | 14 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 | | | 
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 
    0 1 2 3 4 5 6 7 8 9 10 11 12 13 
      ^
      x 

Как вы можете видеть, если вы посмотрите на иллюстрации 6.6 и 6.7, это соответствует ожидаемому поведению.

Таким образом, хотя код не является неправильным, у вас есть одна небольшая зацепка, которая, возможно, выходит за рамки объема книги.

Если тип вставленного типа x является ссылочным типом, вы в текущей куче должны иметь 2 ссылки на тот же самый только что вставленный объект. Если вы тут же удалите объект из кучи, он выглядит (но посмотрите, где выглядит как доставил нас в первую очередь ...), как 0-й элемент, все равно сохранит ссылку, запрещая сборщику мусора выполнять свою работу.

---

Чтобы убедиться, что нет никакой скрытой повестки дня здесь, здесь полный ответ от Марка:

Привет Лассе,

Код корректен.

Бинарная куча - это полное двоичное дерево, в котором по любому пути от до корня значения никогда не увеличиваются. Следовательно, минимальный элемент находится в корне. Представление массива помещает корень в индекс , а для любого узла с индексом i родитель находится в i/2 (округляется вниз) (левый ребенок находится в 2i, а правый - в 2i + 1, но здесь не требуется).

Следовательно, минимальный элемент находится в индексе массива 1, как показано в findMin. Чтобы сделать вставку, вы следуете по пути от нижнего к корням.

В течение цикла:

отверстие/= 2 выражает идею перемещения отверстия к родителю.

x.compareTo (array [hole/2]) < 0 выражает мысль о том, что мы остаемся в циклах, если x меньше родительского.

Проблема в том, что если x является новым минимумом, вы никогда не получите безопасный цикл (технически вы пытаетесь сравнить x и массив [0]). Вы можете поставить дополнительный тест для обработки углового футляра. В качестве альтернативы код обходит это, помещая x в массив [0] в стартом, а так как «родительский» узел i является i/2, «родительский» корень, который находится в индексе 1, может быть найденный в индексе 0. Это гарантирует, что цикл замыкается, если x - новый минимум (а затем помещает x, который является новым минимумом в корневом индексе 1).

Более подробное пояснение содержится в книге ... но основная концепция здесь - - использование значения дозорного (или фиктивного), чтобы избежать дополнительного кода для граничных случаев.

С уважением,

Марк Вайс