heap sort in office line data structure minimum cost code example

Example 1: Heap sort in c++

#include 
 
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);
}

Example 2: heapify down

Heapify down is used when we remove the top element from a heap. Removal of an element is done by swapping the top element with the last element at the bottom of the tree, removing the last element, and then heapfying the new top element down to maintain the heap property. Because this moves down the heap tree, it must perform two comparisons per iteration, with the left child and the right child elements, then swap with the smaller one. Because of this, heapify down is usually more complex to implement than heapify up.