У овом чланку ћемо разговарати о Хеапсорт алгоритму. Хеап сорт обрађује елементе тако што креира мин-хеап или мак-хеап користећи елементе датог низа. Мин-хеап или мак-хеап представља редослед низа у коме основни елемент представља минимални или максимални елемент низа.
Хеап сортирање у основи рекурзивно обавља две главне операције -
- Направите гомилу Х, користећи елементе низа.
- Узастопно бришите основни елемент гомиле формиране у 1стфаза.
Пре него што сазнамо више о сортирању гомиле, хајде да прво погледамо кратак опис Гомила.
Шта је гомила?
Хрпа је потпуно бинарно стабло, а бинарно стабло је дрво у коме чвор може имати највише два детета. Комплетно бинарно стабло је бинарно стабло у коме сви нивои осим последњег нивоа, односно лисног чвора, треба да буду потпуно попуњени, а сви чворови треба да буду поравнати лево.
Шта је сортирање гомиле?
Хеапсорт је популаран и ефикасан алгоритам за сортирање. Концепт сортирања гомиле је да се елементи елиминишу један по један из хеап дела листе, а затим се убацују у сортирани део листе.
Хеапсорт је алгоритам за сортирање на месту.
басх променљива
Сада, да видимо алгоритам сортирања гомиле.
Алгоритам
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
БуилдМакХеап(арр)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
МакХеапифи(арр,и)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
Рад алгоритма сортирања у хрпи
Сада, да видимо како функционише Хеапсорт алгоритам.
У сортирању гомиле, у основи, постоје две фазе које су укључене у сортирање елемената. Користећи алгоритам сортирања гомиле, они су следећи -
- Први корак укључује креирање гомиле прилагођавањем елемената низа.
- Након креирања гомиле, сада више пута уклоните основни елемент гомиле померајући га на крај низа, а затим сачувајте структуру гомиле са преосталим елементима.
Погледајмо детаљно рад сортирања у хрпи користећи пример. Да бисмо то јасније разумели, узмимо несортирани низ и покушамо да га сортирамо користећи сортирање у хрпи. То ће учинити објашњење јаснијим и лакшим.
Прво, морамо да конструишемо хрпу из датог низа и конвертујемо је у максималну хрпу.
Након претварања дате гомиле у максималну, елементи низа су -
Затим морамо да избришемо основни елемент (89) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (Једанаест). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 89 са Једанаест, и претварање гомиле у максималну хрпу, елементи низа су -
У следећем кораку, опет, морамо да избришемо основни елемент (81) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (54). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 81 са 54 и претварање гомиле у максималну хрпу, елементи низа су -
У следећем кораку морамо да избришемо основни елемент (76) поново са максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (9). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 76 са 9 и претварање гомиле у максималну хрпу, елементи низа су -
У следећем кораку, поново морамо да избришемо основни елемент (54) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (14). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 54 са 14 и претварање гомиле у максималну хрпу, елементи низа су -
У следећем кораку, поново морамо да избришемо основни елемент (22) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (Једанаест). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 22 са Једанаест и претварањем гомиле у максималну хрпу, елементи низа су -
У следећем кораку, поново морамо да избришемо основни елемент (14) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (9). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа 14 са 9 и претварање гомиле у максималну хрпу, елементи низа су -
регуларни израз у јава
У следећем кораку, поново морамо да избришемо основни елемент (Једанаест) од максималне гомиле. Да бисмо избрисали овај чвор, морамо га заменити последњим чвором, тј. (9). Након брисања основног елемента, поново морамо да га хеапификујемо да бисмо га претворили у максималну хрпу.
Након замене елемента низа Једанаест са 9, елементи низа су -
Сада, хрпа има само један преостали елемент. Након брисања, хрпа ће бити празна.
Након завршетка сортирања, елементи низа су -
Сада је низ потпуно сортиран.
Сложеност сортирања гомиле
Сада, да видимо временску сложеност Хеап сортирања у најбољем, просечном и најгорем случају. Видећемо и просторну сложеност Хеапсорта.
1. Временска сложеност
| Случај | Временска сложеност |
|---|---|
| Најбољи случај | О(н дневник) |
| Авераге Цасе | О(н лог н) |
| Најгори случај | О(н лог н) |
Временска сложеност сортирања гомиле је О(н дневник) у сва три случаја (најбољи, просечан случај и најгори случај). Висина комплетног бинарног стабла које има н елемената је мирно.
2. Сложеност простора
| Спаце Цомплекити | О(1) |
| Стабилно | Н0 |
- Просторна сложеност Хеап сортирања је О(1).
Имплементација Хеапсорта
Сада, хајде да видимо програме Хеап сортирања у различитим програмским језицима.
Програм: Напишите програм за имплементацију сортирања гомиле у језику Ц.
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>