Heap Sort

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

algorithm:

1. Build a max heap from the input data.
2. now the largest element is at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps while size of heap is greater than 1.

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( arr[], n, i)
{
    largest = i // Initialize largest as root
    l = 2*i + 1 // left = 2*i + 1
    r = 2*i + 2 // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest])

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
    }
}

// main function to do heap sort
void heapSort( arr[], n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i)

    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(arr[0], arr[i])

        // call max heapify on the reduced heap
        heapify(arr, i, 0)
    }
}

we can even using priority queues:

1)take a min heap insert all the elements in the heap

2)now just keep poping the top elements from the heap

void heapSort( arr[], n)
{  
priority_queue< int, vector<int>, greater<int> > pq(arr,arr+k); //min heap

while(!pq.empty())
{
 cout<<pq.top();
  pq.pop();
}

}