Пірамідальне сортування (, «Сортування купою») — алгоритм сортування, працює гарантовано за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O(1)).
Опис алгоритму
Сортування пірамідою використовує бінарне сортувальне дерево. Сортувальне дерево — це таке дерево, у якого виконані умови: Кожен лист має глибину або , або , де — максимальна глибина дерева; Значення в будь-якій вершині не менші (інший варіант — не більші) за значення їх нащадків.
Зручна структура даних для сортувального дерева — такий масив Array, що Array — елемент в корені, а нащадки елемента Array[i] є Array[2i] і Array[2i+1].
Алгоритм сортування складатиметься з двох основних кроків:
1. Вибудовуємо елементи масиву у вигляді сортувального дерева:
при
Цей крок вимагає операцій.
2. Будемо видаляти елементи з кореня по одному за раз і перебудовувати дерево. Тобто на першому кроці обмінюємо Array і Array[n], перетворюємо Array, Array, … , Array[n-1] в сортувальне дерево. Потім переставляємо Array і Array[n-1], перетворюємо Array, Array, … , Array[n-2] в сортувальне дерево. Процес продовжується до тих пір, поки в сортувальному дереві не залишиться один елемент. Тоді Array, Array, … , Array[n] — впорядкована послідовність.
Цей крок вимагає операцій.
Переваги та недоліки
Переваги алгоритму час роботи в найгіршому випадку — ; вимагає додаткової пам'яті.
Недоліки алгоритму нестійкий — для забезпечення стійкості потрібно розширювати ключ; на майже відсортованих даних працює так само довго, як і на хаотичних даних; складний в реалізації; на одному кроці вибірку доводиться робити хаотично по всій довжині масиву — тому алгоритм погано поєднується з кешуванням і (рос. "файлом підкачки", укр. "файлом довантаження") ― віртуальної пам'яті; методу потрібно «миттєвий» прямий доступ; не працює на зв'язаних списках та інших структурах пам'яті послідовного доступу.
Приклади реалізації
C++ #include <iostream> #include <cmath>
using namespace std;
void RestoreHeap(int m[], int father, int last_N) { while(father<=last_N/2)
int maxson=2*father; if (2*father+1<=last_N && m[2*father]<m[2*father+1]) maxson=2*father+1; if (m[maxson]>m[father])
swap(m[maxson],m[father]); father=maxson;
else return;
void HeapSort(int m[], int N) { for (int i=N/2; i>=1; i--) RestoreHeap(m,i,N); for (int i=N; i>1; i--)
swap(m,m[i]); RestoreHeap(m,1,i-1);
void read_mas(int m[],int &N)
cin >> N; for(int i=1;i<=N;i++) cin >> m[i];
void write_mas(int m[],int N) { for(int i=1;i<=N;i++) cout << m[i] << " "; } int main() { int m[100000],N; read_mas(m,N); HeapSort(m,N); write_mas(m,N); return 0; } Java import java.util.Arrays;
public class HeapSort {
public static void main(final String[] args) { final int[] a = { 3,4,5,6,2,23,567,9,1,4,0 }; System.out.println(Arrays.toString(a)); heapSort(a, a.length); System.out.println(Arrays.toString(a));
private static void heapSort(final int[] array, final int count) { heapify(array, count);
int end = count - 1; while (end > 0) { swap(array, end, 0); siftDown(array, 0, --end);
private static void swap(final int[] array, final int a, final int b) { final int temp = array[a]; array[a] = array[b]; array[b] = temp;
private static void heapify(final int[] array, final int count) { int start = count / 2 - 1;
while (start >= 0) { siftDown(array, start, count - 1); start--;
private static void siftDown(final int[] array, final int start, final int end) { int root = start;
while (root * 2 + 1 <= end) { int child = root * 2 + 1; int swap = root; if (array[swap] < array[child]) { swap = child;
if (child + 1 <= end && array[swap] < array[child + 1]) { swap = child + 1;
if (swap != root) { swap(array, root, swap); root = swap; } else { return;
Python def heapSort(li): def downHeap(li, k, n): new_elem = li[k] while k <= n/2: child = 2*k; if child < n and li[child] < li[child+1]: child += 1 if new_elem >= li[child]: break li[k] = li[child] k = child li[k] = new_elem
size = len(li) for i in range(round(size/2-1),-1,-1): downHeap(li, i, size-1) for i in range(size-1,0,-1): temp = li[i] li[i] = li li = temp downHeap(li, 0, i-1) return li
Delphi program Heap_sort_v2; {$APPTYPE CONSOLE} uses SysUtils;
type aint=array [1..20] of integer;
var Arr:aint; n:integer;
procedure change(var a, b:integer); var tmp:integer; begin tmp:=a; a:=b; b:=tmp; end;
procedure rebuild(var A2:aint; f,d:word); var MaxSon:word; begin MaxSon:=f; if (2*f<=d)and(A2[Maxson]<a2[2*f]) then MaxSon:=2*f; if (2*f+1<=d)and(A2[MaxSon]<A2[2*f+1]) then MaxSon:=2*f+1; if MaxSon<>f then begin change(A2[f],A2[MaxSon]); rebuild(A2,MaxSon,d); end; end;
procedure build (var A3:aint; n3:word); var j:word; begin for j:=n3 div 2 downto 1 do rebuild(a3,j,n3); end;
procedure heapsort(var A1:aint; n1:word); var j:word; begin build(a1,n1); for j:=n1 downto 2 do begin change(A1,A1[j]); rebuild(A1,1,j-1); end end;
procedure RndArrInput(var A4:aint; n4:word); var i:word; begin Randomize; for i:=1 to n4 do a4[i]:=random(10)-5; end;
Procedure ArrOutput(var A5:aint; n5:word); var i:word; begin for i:=1 to n5 do write(a5[i],' '); end;
begin Writeln('enter data'); readln(n); RndArrInput(arr,n); ArrOutput(arr,n); heapsort(arr,n); readln; Arroutput(arr,n); writeln('that''s all'); readln; end.
Примітки
Посилання Animated Sorting Algorithms: Heap Sort — графічна демонстрація роботи алгоритму Heapsort Heapsort animated NIST's Dictionary of Algorithms and Data Structures: Heapsort Sorting revisited Java-based demonstration of Heapsort A colored graphical Java applet Хабрахабр — опис сортування купою