Заметил, что в последнее время заинтересовался алгоритмами. Недавно писал статью по ханойским башням, а вчера полностью смог разобраться с алгоритмом пирамидальной сортировки. Как же удивительно то, каким образом у меня все так получается. Четко помню, как в 9-м классе мне пытались объяснить этот алгоритм и то, как его абсолютно не понял. И потом не понял, и спустя 10 лет не понял, и спустя 15 лет не понял, и вот понял только вчера, причем, как же это оказалось просто!
Как же так? Почему то, что ранее не мог разобраться в чем-то десятилетиями, дается так легко сейчас? Что изменилось? Говорят, с возрастом все только хуже становится, но похоже, это не всегда так. Лет 10 назад не мог разобраться ни в чем, а сейчас все даётся пока что довольно легко. Ушел ли у меня страх? Нет, он только добавился и с каждым разом добавляется все больше.
Опишу вкратце, в чем суть алгоритма сортировки пирамидой. Сначала надо построить пирамиду, чтобы самый верхний элемент был самым большим, и два дочерних элементах были либо меньше, либо равны верхнему. И так должно быть для каждого элемента. Для того, чтобы это сделать, первоначально надо привести пирамиду в такой вид. Как это сделать — я тут описывать не буду, но сделать это можно довольно просто.
Так вот, когда наверху самый большой элемент, это и хорошо. То есть, сверху пирамиды всегда будет самый большой элемент, абсолютно всегда, потому что мы это ранее сделали. Теперь же надо убрать этот большой элемент, записать в конец пирамиды снизу, а из конца же пирамиды вытащить другой элемент и поставить в корень. Количество элементов в пирамиде уменьшается на 1. Теперь элемент, который поставили в корень, опускаем вниз так, чтобы он был на своем месте. Это делается за log(n) шагов, то есть, за то количество шагов, какая высота у пирамиды. Если у пирамиды 128 элементов, например, то высота ее 7 слоев. Значит, чтобы привести в порядок пирамиду после перестановки, надо сделать 7 обменов (максимум).
После этого, в корне опять появится самый большой элемент из оставшихся данных. Снова относим в конец (в данном случае на предпоследний элемент бывшей пирамиды), и повторяем до тех пор, пока не остается 1 элемент — это корень. Алгоритм заканчивается.
Ясное дело, что на словах ничего неясно, но я буду статью писать про этот метод сортировки. Однако, это классно, что получилось в этом разобраться. Вообще-то, хотел этот метод сортировки применить для задачи трехмерного рендеринга на ПЛИС, но так не уверен, что дойду вообще до этой задачи. Она не такая сложная, просто надо очень много делать и мне ужасно лень.