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
