Почему нулевой элемент массива кучи не используется?

Question

Вот мой грубый набросок начала кучи с произвольными значениями

 0   1    2    3    4    5    6    7    8    9   ...
[-] [10] [14] [15] [22] [21] [24] [23] [44] [30] ...

Почему элемент в массиве [0] всегда должен быть равен нулю?
Или почему мыне должен использовать это?

Answer 1

Существует несколько способов представления двоичной кучи в виде массива.

Существует способ, при котором используется нулевой элемент;также существует способ, при котором нулевой элемент используется , а не используется:

1. root равен элементу 0;дочерние элементы элемента n являются элементами 2n+1 и 2n+2;
2. корень является элементом 1;дочерние элементы элемента n являются элементами 2n и 2n+1.

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

Itможет показаться, что вы столкнулись с реализацией, которая использует второй подход.Поскольку рассматриваемый язык Java использует массивы с нулями, нулевой элемент существует, но не используется.

Answer 2

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

• Обычно математики используют 1 (один) в качестве индекса первого элемента вектора или первого столбца / строки матрицы.

• По ряду (обоснованных) причин разработчики программного обеспечения используют 0 (ноль). И все современные основные языки программирования делают то же самое.

Возможно, вы встретили описание структуры данных / алгоритмов кучи в каком-то тексте, который был написан кем-то, кто предпочитает «математическое» соглашение соглашению «разработка программного обеспечения». Затем вы закодировали алгоритм в Java, который (как и большинство современных PL) использует массивы, начинающиеся с нуля.

Если вас это беспокоит, просто измените свой код, чтобы вычесть 1 из значений индекса.

---

Обратите внимание, что существуют исключения в области разработки программного обеспечения:

• FORTRAN, COBOL, RPG и несколько других языков программирования - см. Wikipedia .
• Нумерация параметров и столбцов в JDBC.
• Нумерация узлов в DOM API.

---

(Все веские причины, на которые я ссылался, сводятся к тому, что алгоритмы, включающие вычисления индекса, обычно проще, если нулем является индекс первого элемента. Эта статья объясняет это.)

Answer 3

Или почему мы не должны его использовать?

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

Большинство книг по алгоритмам описывают алгоритм, начинающийся с 1 вместо 0.

Вы можете использовать элемент 0, но тогда вам придется изменить свои индексы как ответ @aix.

Некоторые люди считают, что не использовать 0 - пустая трата пространства.
Другие считают, что отсутствие 0 приводит к более читаемому коду.

Выбирай