# Heap-Sort

{% file src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FH1xyJu7GWMFyilWN0Py2%2FPriorityQueues.pdf?alt=media&token=c966696b-41fa-482f-9a56-1c0b744b0221" %}

> We can use any priority queue to develop a sorting method. We insert all the keys to be sorted into a <mark style="color:blue;">minimum-oriented priority queue</mark>, then repeatedly _remove the minimum_ to remove them all in order. When using a heap for the priority queue, we obtain _heapsort_.

Focusing on sorting, we abandon the notion of hiding the heap representation of the priority queue and use <mark style="color:red;">swim()</mark> and <mark style="color:red;">sink()</mark> directly. Doing so allows us to sort an array without needing any extra space, by maintaining the heap within the array to be sorted. Heapsort breaks into two phases: _heap construction_, where we reorganize the original array into a heap, and the _sortdown_, where we pull the items out of the heap in decreasing order to build the sorted result.

* _<mark style="color:blue;">**Heap construction**</mark><mark style="color:blue;">.</mark>_ We can accomplish this task in time proportional to _n_ lg _n_,by proceeding from left to right through the array or bottom-up method, using swim() to ensure that the entries to the left of the scanning pointer make up a heap-ordered complete tree, like successive priority queue insertions. A clever method that is much more efficient is to proceed from right to left, using sink() to make <mark style="color:red;">subheaps</mark> as we go. Every position in the array is the root of a small subheap; sink() works or such subheaps, as well. If the two children of a node are heaps, then calling sink() on that node makes the subtree rooted there a heap.
* _<mark style="color:blue;">**Sortdown.**</mark>_ Most of the work during heapsort is done during the second phase, where we remove the largest remaining items from the heap and put it into the array position vacated as the heap shrinks.



![](https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FmxRsGuqwA8ZJbaffccjU%2Fheapsort-trace.png?alt=media\&token=27d46d77-b1e2-4798-8cad-d217f7e010f6)

{% code title="Max-PQ Heap Sort" %}
```cpp
#include <iostream>
using namespace std;

void sink(char *arr, int k, int n)
{
     while (k * 2 <= n)
     {
          int j = 2 * k;
          if (j < n && arr[j - 1] < arr[j])
               j++;
          if (!(arr[k - 1] < arr[j - 1]))
               break;

          swap(arr[k - 1], arr[j - 1]);
          k = j;
     }
}

void heapSort(char *arr, int size)
{
     int N = size;

     // Heap-Ordered
     for (int k = N / 2; k >= 1; k--)
          sink(arr, k, N);

     // Heap-Sort
     while (N > 1)
     {
          swap(arr[0], arr[--N]);
          sink(arr, 1, N);
     }
}

int main()
{
     char arr[] = {'S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
     int n = sizeof(arr) / sizeof(arr[0]);
     heapSort(arr, n);
     for (int i = 0; i < n; i++)
          cout << arr[i] << " ";
}
```
{% endcode %}

<figure><img src="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FH6XHaec2iAUNVg9MgDx5%2Fimage.png?alt=media&#x26;token=9e53e4fe-3700-4ea2-8e5c-ea96844e626d" alt=""><figcaption></figcaption></figure>

<mark style="color:blue;">Proposition</mark>. Sink-based heap construction is linear time.

\
<mark style="color:blue;">Proposition</mark>. Heapsort users fewer than 2 _n_ lg _n_ compare and exchanges to sort n items.

Most items reinserted into the heap during sortdown go all the way to the bottom. We can thus save time by avoiding the check for whether the item has reached its position, simply promoting the larger of the two children until the bottom is reached, then moving back up the heap to the proper position. This idea cuts the number of compares by a factor of 2 at the expense of extra bookkeeping.
