heap sort without vectors Algorithm
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to efficiently sort elements. It is an in-place sorting algorithm with a time complexity of O(n log n), making it suitable for sorting large datasets. The main idea behind heap sort is to build a binary heap (either max-heap or min-heap) from the input array of elements and then repeatedly extract the root node of the heap, which is either the largest or smallest element, depending on the type of heap used.
The algorithm begins by constructing a max-heap (a binary tree with the largest element at the root) from the input array, ensuring that the parent node is always greater than or equal to its child nodes. Once the max-heap is built, the largest element (the root node) is removed and swapped with the last element in the array. The size of the heap is then reduced by one, and the max-heap property is restored by "heapifying" the new root node, which involves comparing it with its children and swapping it with the largest child if the child is greater. This process of extracting the maximum element, swapping, and heapifying is repeated until the entire array is sorted. In this way, the heap sort algorithm sorts the input array in ascending order.
//
// C++ program for implementation of Heap Sort
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Kaushlendra Pratap
// Github: @kaushl1998
//
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
