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

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

0 голосов
/ 25 декабря 2018

Я пытаюсь понять код для сортировки массива, используя сортировку кучи (ref - 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);        
}

1 Ответ

0 голосов
/ 25 декабря 2018

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

Куча - это двоичное дерево и в массиве индексов на основе 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 heap.Для max_heapify предполагается, что левые и правые поддеревья узла i являются максимальными кучами, но узел i может нарушать свойство максимальной кучи (оно может быть меньше, чем его дочерние элементы).
Это означает, что еслимы вызываем 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]
...