СР5 Пірамідальне сортування

Пірамідальне сортуваня (або сортування за допомогою купи) використовує таку структуру даних, як врівноважене бінарне дерево або, як його ще називають, купа.

Купою називають масив, що має деякі властивості. Щоб легше було їх уявити, представимо масив, як бінарне дерево (дивись рисунок  1). Кожна його вершина відповідає елементу масиву. У вершини з номером i дітьми, якщо вони існують, будуть елементи 2i та 2i+1, а батьком – i div 2. Перший елемент масиву буде коренем дерева.

Головною властивістю купи, яка має обов’язково виконуватись, є правило: A[i div 2]³A[i] (окрім кореня). Звідси випливає, що найбільший елемент дерева знаходиться у корені дерева.

Висотою вершини дерева називається кількість ребер у найдовшому шляху з цієї вершини вниз до листа (вершини, у якої немає синів). Висота дерева, що складає купу з N елементів, дорівнює приблизно log2 N.

Суть методу впорядкування за допомогою купи базується на тому факті, що корінь правильно побудованої купи буде максимальним її елементом. Тому перед впорядкуванням ми робимо з масиву правильну купу, а далі, у процесі сортування, помістивши кореневий (перший) елемент на своє місце, відновлюємо серед решти елементів масиву основну властивість купи.

 

 

Реалізація алгоритму пірамідального сортування на Java