heap sort c with examples
Увод у сортирање гомиле са примерима.
Хеапсорт је једна од најефикаснијих техника сортирања. Ова техника гради хрпу од датог несортираног низа, а затим поново користи хрпу за сортирање низа.
Хеапсорт је техника сортирања заснована на поређењу и користи бинарну гомилу.
=> Прочитајте серију Еаси Ц ++ Траининг Сериес.
како створити нови јава пројекат у ецлипсе-у
Шта ћете научити:
- Шта је бинарна гомила?
- Општи алгоритам
- Илустрација
- Пример Ц ++
- Пример Јаве
- Закључак
- Препоручено читање
Шта је бинарна гомила?
Бинарна гомила је представљена помоћу комплетног бинарног стабла. Потпуно бинарно стабло је бинарно стабло у којем су сви чворови на сваком нивоу потпуно попуњени, осим чворова листова и чворови су колико су лево.
Бинарна гомила или једноставно гомила је комплетно бинарно стабло у којем се ставке или чворови чувају на начин да је коријенски чвор већи од своја два подређена чвора. Ово се такође назива максимална гомила.
Ставке у бинарној хрпи могу се такође сачувати као мин-хеап где је коријенски чвор мањи од своја два подређена чвора. Гомилу можемо представити као бинарно стабло или низ.
Док представља хрпу као низ, под претпоставком да индекс почиње на 0, коријенски елемент се чува на 0. Генерално, ако је родитељски чвор на позицији И, онда је леви подређени чвор на позицији (2 * И + 1) а десни чвор је на (2 * И +2).
Општи алгоритам
Доље је дат општи алгоритам за технику сортирања гомиле.
- Направите максималну хрпу од задатих података тако да је корен највиши елемент хрпе.
- Уклоните роот, тј. Највиши елемент из гомиле и замените га или замените последњим елементом гомиле.
- Затим подесите максималну гомилу, тако да не кршите својства максималне гомиле (хеапифи).
- Горњи корак смањује величину гомиле за 1.
- Поновите горња три корака док се величина гомиле не смањи на 1.
Као што је приказано у општем алгоритму за сортирање датог скупа података у порасту, прво конструишемо максималну гомилу за дате податке.
Узмимо пример за изградњу максималне гомиле са следећим скуповима података.
6, 10, 2, 4, 1
Стабло за овај скуп података можемо конструисати на следећи начин.
У горњем приказу стабла, бројеви у заградама представљају одговарајуће позиције у низу.
Да бисмо конструисали максималну гомилу горњег приказа, морамо испунити услов гомиле да надређени чвор треба да буде већи од његових подређених чворова. Другим речима, дрво треба да „гомиламо“ како бисмо га претворили у мак-хеап.
Након гомилања горњег стабла, добићемо максималну гомилу као што је приказано доле.
Као што је горе приказано, имамо овај мак-хеап генерисан из низа.
Даље, представљамо илустрацију врсте хрпе. Након што смо видели конструкцију мак-хеап-а, прескочићемо детаљне кораке за изградњу мак-хеап-а и директно ћемо приказати мак гомилу у сваком кораку.
Илустрација
Размотрите следећи низ елемената. Морамо сортирати овај низ техником сортирања гомиле.
Конструирајмо мак-хеап како је приказано доле за низ који ће се сортирати.
спајање сортирај низ ц ++
Једном када је гомила конструисана, представљамо је у облику низа као што је приказано доле.
Сада упоређујемо 1стчвор (роот) са последњим чвором, а затим их замените. Дакле, као што је приказано горе, заменимо 17 и 3 тако да је 17 на последњој позицији, а 3 на првој позицији.
Сада уклањамо чвор 17 из гомиле и стављамо га у сортирани низ као што је приказано у осенченом делу испод.
Сада поново градимо гомилу за елементе низа. Овај пут се величина гомиле смањује за 1 јер смо из гомиле избрисали један елемент (17).
Гомила преосталих елемената приказана је испод.
У следећем кораку ћемо поновити исте кораке.
Упоређујемо и замењујемо основни елемент и последњи елемент у гомили.
Након замене, бришемо елемент 12 из гомиле и премештамо га у сортирани низ.
Још једном конструишемо максималну гомилу за преостале елементе као што је приказано доле.
Сада замењујемо корен и последњи елемент, тј. 9 и 3. Након замене, елемент 9 се брише из гомиле и ставља у сортирани низ.
У овом тренутку имамо само три елемента у гомили као што је приказано доле.
Заменимо 6 и 3 и избришемо елемент 6 из гомиле и додамо га у сортирани низ.
Сада конструишемо гомилу преосталих елемената, а затим заменимо оба међусобно.
Након замене 4 и 3, бришемо елемент 4 из гомиле и додајемо га у сортирани низ. Сада имамо само један чвор у хрпи као што је приказано доле .
Дакле, сада је остао само један чвор, ми га бришемо из гомиле и додајемо у сортирани низ.
Стога је горе приказано сортирани низ који смо добили као резултат сортирања гомиле.
На горњој илустрацији сортирали смо низ у растућем редоследу. Ако морамо сортирати низ у опадајућем редоследу, онда морамо следити исте кораке, али са мин-хеап-ом.
Алгоритам Хеапсорт идентичан је сортирању селекције у којем одабиремо најмањи елемент и смештамо га у сортирани низ. Међутим, сортирање гомиле је брже од сортирања избора што се тиче перформанси. Можемо то рећи као да је сорта јача побољшана верзија сортирања избора.
Даље ћемо имплементирати Хеапсорт на Ц ++ и Јава језик.
Најважнија функција у обе имплементације је функција „хеапифи“. Ову функцију позива главна рутина сортирања за преуређивање подстабла када се чвор избрише или када се изгради мак-хеап.
Када смо стабло правилно згушњавали, тек тада ћемо моћи да добијемо исправне елементе у одговарајућим положајима и тако ће низ бити правилно сортиран.
Пример Ц ++
Следи Ц ++ код за имплементацију хепсорта.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Излаз:
Улазни низ
4 17 3 12 9 6
Сортирани низ
3 4 6 9 12 17
Даље ћемо имплементирати хепсорт на Јава језику
Пример Јаве
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Излаз:
Улазни низ:
4 17 3 12 9 6
Сортирани низ:
3 4 6 9 12 17
алтернатива ццлеанер-у за Виндовс 10
Закључак
Хеапсорт је техника сортирања заснована на поређењу помоћу бинарне хрпе.
То се може назвати побољшањем у односу на сортирање избора, јер обе ове технике сортирања раде са сличном логиком поновног проналажења највећег или најмањег елемента у низу, а затим га стављања у сортирани низ.
Хеап сорт користи мак-хеап или мин-хеап за сортирање низа. Први корак у сортирању гомиле је изградња мин или мак гомиле из података низа, а затим рекурзивно брисање коријенског елемента и гомилање гомиле док у гомили не постоји само један чвор.
Хеапсорт је ефикасан алгоритам и изводи се брже од сортирања одабира. Може се користити за сортирање готово сортираног низа или проналажење к највећих или најмањих елемената у низу.
Овим смо завршили нашу тему о техникама сортирања у Ц ++. Од нашег следећег водича надаље, започињемо са структурама података једну по једну.
=> Овде потражите целу серију обука за Ц ++.
Препоручено читање
- МонгоДБ метода сортирања () са примерима
- Уник наредба за сортирање са синтаксом, опцијама и примерима
- Споји сортирање у Ц ++ са примерима
- Сортирање љуске на Ц ++ са примерима
- Сортирање уметања у Ц ++ са примерима
- Сортирање избора у Ц ++ са примерима
- Мехурићи сортирани на Ц ++ са примерима
- Брзо сортирање у Ц ++ са примерима