MinHeap Удалить Понимание

Question

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

Дайте псевдокод для процедуры Min-Heap-Delete (A, k).Предположим, что ключ k находится в местоположении l кучи и что 1 ≤ l ≤ n.

Мое решение состоит в том, что

Обмен A [k] сA [A.size () - 1]

A.size () = A.size () - 1

Мин-куча (A, k)

Однако мое решение отличается от решения профессора в первой части.

Обмен A [k] на A [A.heap_size ()]

A.heap_size () = A.heap_size () - 1

Мин-куча (A, k)

Зачем намиспользовать A.size () вместо A.size () - 1?Не будет ли A.size () индексировать массив, представляющий кучу, поскольку куча начинается с индекса 1?

В этом случае A.size () даст нам 10. Однако A [10] не существует и может вызвать ошибку.Поэтому, почему не A [10-1] получить последний узел в дереве кучи?

Answer 1

Потому что профессор использует нумерацию на основе 1 вместо нуля.Примечание 1 ≤ l ≤ n состояние.И вы, вероятно, пропустили, что индекс равен A. heap_size - размер кучи, а не размер массива, поэтому последний элемент будет называться A[9]

Это довольно распространенная практика и удобная для куч, потому чтоОтношения между дочерним и родительским индексами выглядят очень просто:

childs = parent * 2 and parent * 2 + 1
parent = child / 2

Обратите внимание, что массив на рисунке действительно основан на зео с неиспользуемой нулевой записью