Heapsort: объяснение процедуры построения максимальной кучи

Question

Я пытаюсь понять код для сортировки массива с помощью Heap Sort (ссылка - https://www.sanfoundry.com/java-program-implement-heap-sort/)

Функция "maxheap" использует этот расчет для получения левого и правого потомков узла (то же самое используется в нескольких различных примерах / сайтах)

int left = 2 * i;
int right = 2 * i + 1;

Какова логика / обоснование вышесказанного?

Кроме того, в функции heapify, maxheap fn вызывается с i = N / 2 -> 0
(вместо i = 0 до N -1, например.) Есть идеи, почему это делается?

public static void heapify(int arr[])
{
     N = arr.length-1;
     for (int i = N/2; i >= 0; i--)
         maxheap(arr, i);        
}

Answer 1

Какова логика / обоснование вышесказанного?

Куча - это двоичное дерево и в массиве индексов на основе 1, как показано ниже, чтобы получить левого потомка узла i вам нужен индекс 2*i и для правильного ребенка вы получаете индекс 2*i + 1,

Array:
[1, 2, 3, 4, 5, 6, 7]

Binary tree:

         1
      /     \
   2           3
 /   \       /   \
4     5     6     7

Кроме того, в функции heapify функция maxheap fn вызывается с i = N/2 -> 0 (например, вместо i = 0 - N -1). Есть идеи, почему это делается?

maxheap или же max_heapify функция представляет собой процедуру, которая получает массив и индекс i в качестве входных данных для поддержания свойства максимальной кучи. Предположение для max_heapify является то, что левое и правое поддеревья узла i это максимальные кучи, но узел i может нарушать свойство max heap (оно может быть меньше, чем его дочерние элементы).
Это означает, что если мы позвоним max_heapify на всех элементах массива все узлы будут поддерживать свойство max heap, и мы должны получить максимальную кучу. Однако если мы начнем с начала массива (корень дерева), мы не сможем предположить, что левое и правое поддеревья уже являются максимальными кучами, поэтому нам нужно начать с конца (листья дерева) и перейти к началу. Кроме того, у листьев нет детей, так что они уже тривиально, и нам не нужно звонить max_heapify на них. В куче из n элементов узлы в подмассиве [floor(n/2)+1..n] листья, поэтому мы можем от floor(n/2) в 1 и позвонить max_heapify только на внутренних узлах.

Для массива на основе 0:

left(i):        2 * i + 1
right(i):       2 * i + 2
leaves:         [floor(n/2)..n-1]
internal nodes: [0..floor(n/2)-1]