Heap sort requires us to build a heap from a given list of elements and then continuously checks the heap property so that the whole heap remains sorted all the time. Unlike a regular heap where we stop checking the heap property once the newly inserted value satisfies the conditions, we continue to do so for the next elements during the heap sort implementation. The pseudocode of the heap sort looks like this:

Heapsort(A as array) 
    BuildHeap(A) 
    for i = n-1 to 0 
        swap(A[0], A[i]) 
        n = n - 1 
        Heapify(A, 0) 

BuildHeap(A as array) 
    n = elements_in(A) 
    for i = floor(n/2) to 0 
        Heapify(A,i) 

Heapify(A as array, i as int) 
    left = 2i+1 
    right = 2i+2 
    max = i 

    if (left <= n) and (A[left] > A[i]) 
        max = left 

    if (right<=n) and (A[right] > A[max]) 
        max = right 

    if (max != i) 
        swap(A[i], A[max]) 
        Heapify(A, max) 

The pseudocode shows that whenever we are trying to sort a list of elements, the start process depends on building the heap. Each time we add an item to the heap, we check if that satisfies heap properties through the heapify function. Once the heap is built, we check the heap properties of all elements. Let us now implement the heap sort based on the preceding pseudocode:

function heapSort(array &$a) { 
    $length = count($a); 
    buildHeap($a); 
    $heapSize = $length - 1; 
    for ($i = $heapSize; $i >= 0; $i--) { 
      $tmp = $a[0]; 
      $a[0] = $a[$heapSize]; 
      $a[$heapSize] = $tmp; 
      $heapSize--; 
      heapify($a, 0, $heapSize); 
    } 
} 

function buildHeap(array &$a) { 
    $length = count($a); 
    $heapSize = $length - 1; 
    for ($i = ($length / 2); $i >= 0; $i--) { 
        heapify($a, $i, $heapSize); 
    } 
} 

function heapify(array &$a, int $i, int $heapSize) { 
    $largest = $i; 
    $l = 2 * $i + 1; 
    $r = 2 * $i + 2; 
    if ($l <= $heapSize && $a[$l] > $a[$i]) { 
        $largest = $l; 
    } 

    if ($r <= $heapSize && $a[$r] > $a[$largest]) { 
        $largest = $r; 
    } 

    if ($largest != $i) { 
      $tmp = $a[$i]; 
      $a[$i] = $a[$largest]; 
      $a[$largest] = $tmp; 
      heapify($a, $largest, $heapSize); 
    } 
} 

Let us now use the heapSort function to sort an array. Since we are passing the argument as by reference, we are not returning anything from the function. The actual array will be sorted at the end of the operation:

$numbers = [37, 44, 34, 65, 26, 86, 143, 129, 9]; 
heapSort($numbers); 
echo implode("	", $numbers); 

If we run this code, it will have the following output in the command line:

9       26      34      37      44      65      86      129     143

If we want to change the sorting to descending order, we just need to change the comparison in the heapify function. If we consider time and space complexity for the heapSort algorithm, we will see that heap sort has the best complexity for a sorting algorithm:

Compared to merge sort, heap sort has better space complexity. As a result, many developers prefer heap sort for sorting lists of items.