Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Пірамідальне сортування (англ. Heapsort, «Сортування купою») — алгоритм сортування, працює гарантовано за Θ(n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O(1)).
 | |
| Клас | Алгоритм сортування |
|---|---|
| Структура даних | масив |
| Найгірша швидкодія | |
| Найкраща швидкодія | |
| Середня швидкодія | |
| Просторова складність у найгіршому випадку | основний, допоміжний |
| Оптимальний | Інколи |
| Стабільний | Нестійка |
Опис алгоритму
| Ця стаття потребує для відповідності Вікіпедії. |
Сортування пірамідою використовує бінарне сортувальне дерево. Сортувальне дерево — це таке дерево, у якого виконані умови:
- Кожен лист має глибину або
![image]()
, або ![image]()
, де ![image]()
— максимальна глибина дерева; - Значення в будь-якій вершині не менші (інший варіант — не більші) за значення їх нащадків.
Зручна структура даних для сортувального дерева — такий масив Array, що Array[1] — елемент в корені, а нащадки елемента Array[i] є Array[2i] і Array[2i+1].
Алгоритм сортування складатиметься з двох основних кроків:
1. Вибудовуємо елементи масиву у вигляді сортувального дерева:
при 
Цей крок вимагає 
операцій.
2. Будемо видаляти елементи з кореня по одному за раз і перебудовувати дерево. Тобто на першому кроці обмінюємо Array[1] і Array[n], перетворюємо Array[1], Array[2], … , Array[n-1] в сортувальне дерево. Потім переставляємо Array[1] і Array[n-1], перетворюємо Array[1], Array[2], … , Array[n-2] в сортувальне дерево. Процес продовжується до тих пір, поки в сортувальному дереві не залишиться один елемент. Тоді Array[1], Array[2], … , Array[n] — впорядкована послідовність.
Цей крок вимагає 
операцій.
Переваги та недоліки
Переваги алгоритму
- час роботи в найгіршому випадку —
![image]()
; - вимагає
![image]()
додаткової пам'яті.
Недоліки алгоритму
- нестійкий — для забезпечення стійкості потрібно розширювати ключ;
- на майже відсортованих даних працює так само довго, як і на хаотичних даних;
- складний в реалізації;
- на одному кроці вибірку доводиться робити хаотично по всій довжині масиву — тому алгоритм погано поєднується з кешуванням і (рос. "файлом підкачки", укр. "файлом довантаження") ― віртуальної пам'яті;
- методу потрібно «миттєвий» прямий доступ; не працює на зв'язаних списках та інших структурах пам'яті послідовного доступу.
Приклади реалізації
#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[1],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; } 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; } } } } 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[0] li[0] = temp downHeap(li, 0, i-1) return li 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[1],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 — графічна демонстрація роботи алгоритму
- NIST's Dictionary of Algorithms and Data Structures: Heapsort
- Sorting revisited
- Хабрахабр — опис сортування купою
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Piramidalne sortuvannya angl Heapsort Sortuvannya kupoyu algoritm sortuvannya pracyuye garantovano za 8 n log n operacij pri sortuvanni n elementiv Kilkist zastosovuvanoyi sluzhbovoyi pam yati ne zalezhit vid rozmiru masivu tobto O 1 Piramidalne sortuvannyaPriklad sortuvannya vipadkovogo naboru chisel za algoritmom piramidalne sortuvannya Priklad sortuvannya vipadkovogo naboru chisel za algoritmom piramidalnogo sortuvannya KlasAlgoritm sortuvannyaStruktura danihmasivNajgirsha shvidkodiyaO nlog n displaystyle O n log n Najkrasha shvidkodiyaW n O nlog n displaystyle Omega n O n log n Serednya shvidkodiyaO nlog n displaystyle O n log n Prostorova skladnist u najgirshomu vipadkuO n displaystyle O n osnovnij O 1 displaystyle O 1 dopomizhnijOptimalnijInkoliStabilnijNestijkaOpis algoritmuPriklad sortuvalnogo derevaStruktura zberigannya danih sortuvalnogo derevaCya stattya potrebuye uporyadkuvannya dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit polipshiti cyu stattyu Mozhlivo mistit zauvazhennya shodo potribnih zmin Sortuvannya piramidoyu vikoristovuye binarne sortuvalne derevo Sortuvalne derevo ce take derevo u yakogo vikonani umovi Kozhen list maye glibinu abo d displaystyle d abo d 1 displaystyle d 1 de d displaystyle d maksimalna glibina dereva Znachennya v bud yakij vershini ne menshi inshij variant ne bilshi za znachennya yih nashadkiv Zruchna struktura danih dlya sortuvalnogo dereva takij masiv Array sho Array 1 element v koreni a nashadki elementa Array i ye Array 2i i Array 2i 1 Algoritm sortuvannya skladatimetsya z dvoh osnovnih krokiv 1 Vibudovuyemo elementi masivu u viglyadi sortuvalnogo dereva Array i Array 2i displaystyle text Array i geq text Array 2i Array i Array 2i 1 displaystyle text Array i geq text Array 2i 1 pri 1 i lt n 2 displaystyle 1 leq i lt n 2 Cej krok vimagaye O n displaystyle O n operacij 2 Budemo vidalyati elementi z korenya po odnomu za raz i perebudovuvati derevo Tobto na pershomu kroci obminyuyemo Array 1 i Array n peretvoryuyemo Array 1 Array 2 Array n 1 v sortuvalne derevo Potim perestavlyayemo Array 1 i Array n 1 peretvoryuyemo Array 1 Array 2 Array n 2 v sortuvalne derevo Proces prodovzhuyetsya do tih pir poki v sortuvalnomu derevi ne zalishitsya odin element Todi Array 1 Array 2 Array n vporyadkovana poslidovnist Cej krok vimagaye O nlog n displaystyle O n log n operacij Perevagi ta nedolikiPerevagi algoritmu chas roboti v najgirshomu vipadku O nlog n displaystyle O n log n vimagaye O 1 displaystyle O 1 dodatkovoyi pam yati Nedoliki algoritmu nestijkij dlya zabezpechennya stijkosti potribno rozshiryuvati klyuch na majzhe vidsortovanih danih pracyuye tak samo dovgo yak i na haotichnih danih skladnij v realizaciyi na odnomu kroci vibirku dovoditsya robiti haotichno po vsij dovzhini masivu tomu algoritm pogano poyednuyetsya z keshuvannyam i ros fajlom pidkachki ukr fajlom dovantazhennya virtualnoyi pam yati metodu potribno mittyevij pryamij dostup ne pracyuye na zv yazanih spiskah ta inshih strukturah pam yati poslidovnogo dostupu Prikladi realizaciyiC include lt iostream gt include lt cmath gt using namespace std void RestoreHeap int m int father int last N while father lt last N 2 int maxson 2 father if 2 father 1 lt last N amp amp m 2 father lt m 2 father 1 maxson 2 father 1 if m maxson gt m father swap m maxson m father father maxson else return void HeapSort int m int N for int i N 2 i gt 1 i RestoreHeap m i N for int i N i gt 1 i swap m 1 m i RestoreHeap m 1 i 1 void read mas int m int amp N cin gt gt N for int i 1 i lt N i cin gt gt m i void write mas int m int N for int i 1 i lt N i cout lt lt m i lt lt 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 gt 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 gt 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 lt end int child root 2 1 int swap root if array swap lt array child swap child if child 1 lt end amp amp array swap lt 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 lt n 2 child 2 k if child lt n and li child lt li child 1 child 1 if new elem gt 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 0 li 0 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 lt d and A2 Maxson lt a2 2 f then MaxSon 2 f if 2 f 1 lt d and A2 MaxSon lt A2 2 f 1 then MaxSon 2 f 1 if MaxSon lt gt 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 1 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 Primitkihttp dx doi org 10 1006 jagm 1993 1031PosilannyaAnimated Sorting Algorithms Heap Sort grafichna demonstraciya roboti algoritmu NIST s Dictionary of Algorithms and Data Structures Heapsort Sorting revisited Habrahabr opis sortuvannya kupoyu