heap sort c with examples
Въведение в сортирането на купчина с примери.
Heapsort е една от най-ефективните техники за сортиране. Тази техника изгражда купчина от дадения несортиран масив и след това отново използва купчината за сортиране на масива.
Heapsort е техника за сортиране, базирана на сравнение и използва двоична купчина.
=> Прочетете серията Easy C ++ Training.
как да създадете нов java проект в eclipse
Какво ще научите:
- Какво е двоична купчина?
- Общ алгоритъм
- Илюстрация
- Пример за C ++
- Пример за Java
- Заключение
- Препоръчително четене
Какво е двоична купчина?
Бинарната купчина е представена с помощта на пълно двоично дърво. Пълното двоично дърво е двоично дърво, в което всички възли на всяко ниво са напълно запълнени, с изключение на листните възли и възлите са до ляво.
Двоична купчина или просто купчина е цялостно двоично дърво, където елементите или възлите се съхраняват по такъв начин, че коренният възел да е по-голям от двата си дъщерни възела. Това се нарича още максимална купчина.
Елементите в двоичната купчина също могат да се съхраняват като min-heap, при което коренният възел е по-малък от двата си дъщерни възела. Можем да представим купчина като двоично дърво или масив.
Докато представлява купчина като масив, ако приемем, че индексът започва от 0, коренният елемент се съхранява на 0. Като цяло, ако родителски възел е в позиция I, тогава левият дъщерен възел е в позицията (2 * I + 1) и десният възел е на (2 * I +2).
Общ алгоритъм
По-долу е даден общият алгоритъм за техниката за сортиране на купчини.
- Изградете максимална купчина от дадените данни, така че коренът да е най-високият елемент на купчината.
- Премахнете корена, т.е. най-високия елемент от купчината и го заменете или заменете с последния елемент от купчината.
- След това коригирайте максималната купчина, за да не нарушите свойствата на максималната купчина (heapify).
- Горната стъпка намалява размера на купчината с 1.
- Повторете горните три стъпки, докато размерът на купчината се намали до 1.
Както е показано в общия алгоритъм за сортиране на дадения набор от данни в нарастващ ред, първо конструираме максимална купчина за дадените данни.
Нека вземем пример за изграждане на максимална купчина със следния набор от данни.
6, 10, 2, 4, 1
Можем да изградим дърво за този набор от данни, както следва.
В горното представяне на дървото числата в скобите представляват съответните позиции в масива.
За да изградим максимална купчина от горното представяне, трябва да изпълним условието за купчината, че родителският възел трябва да е по-голям от неговите дъщерни възли. С други думи, трябва да „натрупаме“ дървото, за да го преобразуваме в max-heap.
След натрупване на горното дърво ще получим максималната купчина, както е показано по-долу.
Както е показано по-горе, имаме тази максимална купчина, генерирана от масив.
След това представяме илюстрация на сортиране на купчина. След като видяхме изграждането на max-heap, ще пропуснем подробните стъпки за изграждане на max-heap и директно ще покажем max heap на всяка стъпка.
Илюстрация
Обмислете следния масив от елементи. Трябва да сортираме този масив, използвайки техниката за сортиране на купчини.
Нека конструираме max-heap, както е показано по-долу, за масива, който ще бъде сортиран.
След като купчината е конструирана, ние я представяме под формата на масив, както е показано по-долу.
Сега сравняваме 1улвъзел (корен) с последния възел и след това ги разменете. По този начин, както е показано по-горе, ние сменяме 17 и 3, така че 17 е на последната позиция, а 3 е на първата позиция.
Сега премахваме възела 17 от купчината и го поставяме в сортирания масив, както е показано в засенчената част по-долу.
Сега отново конструираме купчина за елементите на масива. Този път размерът на купчината се намалява с 1, тъй като изтрихме един елемент (17) от купчината.
Купчината от останалите елементи е показана по-долу.
В следващата стъпка ще повторим същите стъпки.
Сравняваме и разменяме основния елемент и последния елемент в купчината.
След размяната изтриваме елемента 12 от купчината и го преместваме в сортирания масив.
най-добрият изтеглящ mp3 за android без реклами
За пореден път конструираме максимална купчина за останалите елементи, както е показано по-долу.
Сега разменяме корена и последния елемент, т.е. 9 и 3. След размяната, елемент 9 се изтрива от купчината и се поставя в сортиран масив.
В този момент имаме само три елемента в купчината, както е показано по-долу.
Разменяме 6 и 3 и изтриваме елемента 6 от купчината и го добавяме към сортирания масив.
Сега конструираме купчина от останалите елементи и след това сменяме и двете помежду си.
След размяна на 4 и 3, изтриваме елемент 4 от купчината и го добавяме към сортирания масив. Сега имаме само един възел, останал в купчината, както е показано по-долу .
Така че сега, когато остава само един възел, го изтриваме от купчината и го добавяме към сортирания масив.
По този начин показаното по-горе е сортираният масив, който сме получили в резултат на сортирането на купчината.
В горната илюстрация сме сортирали масива във възходящ ред. Ако трябва да сортираме масива в низходящ ред, тогава трябва да следваме същите стъпки, но с min-heap.
Алгоритъмът за сортиране е идентичен със сортирането на селекцията, при което избираме най-малкия елемент и го поставяме в сортиран масив. Сортирането на купчината обаче е по-бързо от сортирането на селекцията, що се отнася до производителността. Можем да го кажем, тъй като купчината е подобрена версия на сорта за избор.
След това ще внедрим Heapsort в C ++ и Java език.
Най-важната функция и в двете имплементации е функцията “heapify”. Тази функция се извиква от основната рутинна купчина за пренареждане на поддървото, след като възел бъде изтрит или когато е изградена максимална купчина.
Когато сме натрупали дървото правилно, само тогава ще можем да получим правилните елементи в правилните им позиции и по този начин масивът ще бъде сортиран правилно.
Пример за C ++
Следва кодът на C ++ за изпълнение на купчина.
#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
Пример за Java
// 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 Изход:
Входен масив:
как да отворите JSON файл на Windows
4 17 3 12 9 6
Сортиран масив:
3 4 6 9 12 17
Заключение
Heapsort е базирана на сравнение техника за сортиране, използваща двоична купчина.
Може да се нарече подобрение спрямо сортирането на селекцията, тъй като и двете техники за сортиране работят с подобна логика на многократно намиране на най-големия или най-малкия елемент в масива и след това поставянето му в сортирания масив.
Heap sort използва max-heap или min-heap за сортиране на масива. Първата стъпка при сортирането на купчината е да се изгради минимална или максимална купчина от данните на масива и след това да се изтрие кореновият елемент рекурсивно и да се натрупа купчината, докато в купчината има само един възел.
Хепсортът е ефективен алгоритъм и се изпълнява по-бързо от сортирането по избор. Може да се използва за сортиране на почти сортиран масив или намиране на k най-големи или най-малки елементи в масива.
С това завършихме нашата тема за техниките за сортиране в C ++. От следващия урок нататък ще започнем със структури от данни един по един.
=> Потърсете тук цялата серия за обучение на C ++.
Препоръчително четене
- Метод за сортиране на MongoDB () с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Обединяване на сортиране в C ++ с примери
- Сортиране на черупката в C ++ с примери
- Сортиране по вмъкване в C ++ с примери
- Сортиране на избора в C ++ с примери
- Сортиране на балончета в C ++ с примери
- Бързо сортиране в C ++ с примери