heap
A heap is a tree-based data structure in which all the nodes of the tree are in a specific order. For example, if is the parent node of , then the value of follows a specific order with respect to the value of and the same order will be followed across the tree.
heap
void max_heapify (int Arr[ ], int i, int N) { int left = 2*i //left child int right = 2*i +1 //right child if(left<= N and Arr[left] > Arr[i] ) largest = left; else largest = i; if(right <= N and Arr[right] > Arr[largest] ) largest = right; if(largest != i ) { swap (Arr[i] , Arr[largest]); max_heapify (Arr, largest,N); } }
heapsort
Implementation of heap sort in C++: #include <bits/stdc++.h> using namespace std; // To heapify a subtree rooted with node i which is // Heapify:- A process which helps regaining heap properties in tree after removal void heapify(int A[], int n, int i) { int largest = i; // Initialize largest as root int left_child = 2 * i + 1; // left = 2*i + 1 int right_child = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (left_child < n && A[left_child] > A[largest]) largest = left_child; // If right child is larger than largest so far if (right_child < n && A[right_child] > A[largest]) largest = right_child; // If largest is not root if (largest != i) { swap(A[i], A[largest]); // Recursively heapify the affected sub-tree heapify(A, n, largest); } } // main function to do heap sort void heap_sort(int A[], int n) { // Build heap (rearrange array) 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 to end swap(A[0], A[i]); // call max heapify on the reduced heap heapify(A, i, 0); } } /* A function to print sorted Array */ void printArray(int A[], int n) { for (int i = 0; i < n; ++i) cout << A[i] << " "; cout << "\n"; } // Driver program int main() { int A[] = { 22, 19, 3, 25, 26, 7 }; // array to be sorted int n = sizeof(A) / sizeof(A[0]); // n is size of array heap_sort(A, n); cout << "Sorted array is \n"; printArray(A, n); }
Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
