Max Heapify-псевдокод

Я запутался в одной части этого псевдокода для Max Heap Sort. Что означает до 2?

HeapSort(A)
Build-Max-Heap(A)
for i <-- length[A] down to 2
do exchange A[1] <---> A[i]
heap-size[A] =  heap-size[A] -1
Max-Heapify(A,1)

algorithm language-agnostic heapsort max-heap
person user7941837    schedule 29.04.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Это означает, что вы повторяете этот блок для каждого значения i в {length[A], length[A] - 1, length[A] - 2, ..., 2}.

Если бы это был C (или C++, или Java — все тот же синтаксис для этого), можно было бы написать это:

for (int i = length(A), i >= 2, i--) {
    do...
}
person Arya McCarthy    schedule 29.04.2017

arrow_upward
0
arrow_downward

Heapsort — это, по сути, сортировка выбором, но несортированная часть массива хранится в виде структуры данных maxheap. Более конкретно, пирамидальная сортировка работает следующим образом. Сначала выбирает самый большой элемент в массиве A[1..n] и меняет его местами с A[n]. Затем выберите самый большой элемент в массиве A[1..n-1] и замените его на A[n-1]. Повторяйте этот процесс, пока на последней итерации мы не найдем самый большой элемент в A[1..2] и не заменим его на A[2]. В этот момент элементы A[2..n] находятся в правильном положении, поэтому A[1] также находится в правильном положении, и массив отсортирован.

Это почти похоже на сортировку выбором (где мы выбираем самый большой элемент из A[1..i] и меняем его местами с A[i]), за исключением того, что в heapsort A[1..i] хранится с использованием структуры данных, называемой maxheap, так что процесс выбора наибольшего элемента выполняется не с использованием линейного поиска (как в сортировке выбором), а путем максимизации массива и, таким образом, переноса наибольшего элемента на первую позицию A[1]. Следовательно, поиск наибольшего элемента занимает логарифмическое время, а не линейное время.

Приведенный выше алгоритм можно сформулировать так: для i=n, ​​n-1,..., 2 (в указанном порядке) найти наибольший элемент в A[1..i] и поменять его местами с A[i]. Поскольку i принимает значения в этом порядке убывания, цикл for можно записать так: for i = n вплоть до 2.

person Ashwin Ganesan    schedule 30.04.2017