Пирамидальная сортировка HeapSort. Пирамида Хеопса
Пирамидальная сортировка основана на алгоритме построения пирамиды. Определение Последовательность aL , aL+1 , … , aR называется пирамидой, если неравенство ai ≤ min (a2i , a2i+1 ) выполняется для всех i, для которых хотя бы один из элементов a2i и a2i+1 существует. Пирамидальная сортировка
или метод Вильямса – Флойда
( Williams, Floyd, 1964) Пример 2 3 4 5 6 7 8 - пирамида 3 2 6 3 4 5 7 1 2 3 4 5 6 7 - не пирамида 1. Двустороннее усечение: Если последовательность aL, aL+1 , ..., аR-1, aR – пирамида, то aL+1 , ..., aR-1 тоже пирамида. 2. Если a1 , a2 , ..., an – пирамида, то а1 – минимальный элемент пирамиды. 3. Если a1 , ..., an – произвольная последовательность, то an/2 , .., an – пирамида. Свойства пирамиды