Implementing heap sort algorithm in C++

Heapsort is a comparison-based sorting algorithm to create a sorted array, and is part of the selection sort family.

Heap sort build the max heap first. The max heap is where the highest element is at the front of the array. Once max heap is built then swap the highest element to end.

Now minimize the size of heap by and fulfill the max heap property. So that highest from the remaining array will be at the front. Now again swap this with second last element from the array. Follow this process till first element.

typedef vector<int> IntVect; inline int Left(int i) {     return (2 *  i); } inline int Right(int i) {     return ((2 * i) + 1); } void MaxHeapify(IntVect & A, int i, int end) {     int left = Left(i);     int right = Right(i);     int max = i;     if (left < end && A[left] > A[max])         max = left;     if (right < end && A[right] > A[max])         max = right;     if (max != i)     {         SwapInts(A[max], A[i]);         MaxHeapify(A, max, end);     } } void BuildMaxHeap(IntVect & A, int end) {     for (int i = end / 2; i >= 0 ; i--)     {         MaxHeapify(A, i, end);     } } void HeapSort(IntVect & A) {     BuildMaxHeap(A, A.size());     for (int i = A.size() - 1; i > 0; i--)     {         SwapInts(A[0], A[i]);         MaxHeapify(A, 0, i);     } }

The BuildMaxHeap method can be used for creating the priority queue as well.