Comments 4
Для более простого объяснения алгоритм достаточно назвать «царь горы». Это более наглядное название происходящего.
В C# этот алгоритм может использоваться наравне с QuickSort при сортировке массива.
Построение пирамиды — O(N) по времени. Почему так? На самом деле формирование кучи можно описать по другому. Мы идем с середины массива, и делаем просеивания для элементов на уровнях, без рекурсивного вызова. Допустим для упрощения, длина массива N = 2^n — 1, пирамида ровненькая. Просеивания для нижнего уровня нелистовых элементов — высотой 1, таких элементов N/4. Для уровня выше высота будет 2, там N/8 элементов, потом 3 и N/16 элементов, и т.д. Если это дело просуммировать, то получаем O(N)
Sign up to leave a comment.
Пирамидальная сортировка выбором