Почему в куче, реализованном массивом, индекс 0 остается неиспользованным?

Ответ 1

Нет причин, по которым куча, реализованная в массиве, должна оставлять элемент с индексом 0 неиспользованным. Если вы установите корень в 0, то у элемента в array[index] дочерние элементы в array[index] array[index*2+1] и array[index*2+2]. Узел в array[child] имеет своего родителя в array[(child-1)/2].

Давай посмотрим.

                  root at 0       root at 1
Left child        index*2 + 1     index*2
Right child       index*2 + 2     index*2 + 1
Parent            (index-1)/2     index/2

Таким образом, наличие корня в 0, а не в 1 стоит вам дополнительного сложения, чтобы найти левого потомка, и дополнительного вычитания, чтобы найти родителя.

Для более общего случая, когда это может быть не двоичная куча, а 3-кучная, 4-кучная и т.д., Где для каждого узла вместо 2 используются дочерние элементы NUM_CHILDREN, используются следующие формулы:

                  root at 0                  root at 1
Left child        index*NUM_CHILDREN + 1     index*NUM_CHILDREN
Right child       index* NUM_CHILDREN + 2    index*NUM_CHILDREN + 1
Parent            (index-1)/NUM_CHILDREN     index/NUM_CHILDREN

Я не вижу этих нескольких дополнительных инструкций, которые бы сильно повлияли на время выполнения.

По причинам, по которым я считаю неправильным начинать с 1 на языке с массивами на основе 0, см. fooobar.com/questions/15497843/... и мой пост в блоге. Но это так, как мы всегда это делали!

Ответ 2

Как я нашел в книге CLRS, есть некоторое значение с точки зрения производительности, поскольку, как правило, операторы сдвига работают очень быстро.

На большинстве компьютеров процедура LEFT может вычислять 2*i в одной инструкции посредством просто смещение двоичного представления i, оставленного одной битовой позицией. Аналогичным образом, Правильная процедура может быстро вычислить 2*i+1, сдвинув двоичное представлениеиз я оставлен одной битовой позицией, а затем добавляется в 1 как младший бит. Процедура PARENT может вычислять i/2 с помощью смещения я правой позиции в битах.

Итак, начало кучи в индексе 1, вероятно, сделает более быстрое вычисление родительских, левых и правых дочерних индексов.

Ответ 3

Как заметил AnonJ, речь идет скорее о вкусе, чем о технической необходимости. Одна хорошая вещь, начиная с 1, а не 0, состоит в том, что существует биекция между двоичными строками x и положительными целыми числами, которая отображает двоичную строку x в положительное целое число, записанное 1x в двоичном формате. Строка x указывает путь от корня к индексированному node, где 0 означает "взять левого ребенка", а 1 означает "взять правильный ребенок".

Другое соображение состоит в том, что в противном случае неиспользуемое "нулевое" местоположение может содержать дозорный элемент со значением минус бесконечность, который на архитектурах без предсказания ветвления может означать незначительное улучшение времени выполнения из-за того, что у него есть только один тест в просеивании вверх а не два.

Ответ 4

(Пока я искал, я придумал свой ответ, но я не знаю, правильно это или нет.)

Если для корня node используется индекс 0, последующие вычисления его дочерних элементов не могут выполняться, потому что мы имеем indexOfLeftChild = indexOfParent * 2 и indexOfRightChild = indexOfParent * 2 + 1. Однако 0 * 2 = 0 и 0 * 2 + 1 = 1, которые не могут представлять отношения родитель-дети, которые мы хотим. Поэтому мы должны начинать с 1, чтобы дерево, представленное массивом, соответствовало математическим свойствам, которые мы желаем.