Sorting

Nov 22, 2023

---

Heap Sort

The binary heap data structure is a array data structure as a almost full binary tree. Here is a provided way to implement to compute the indices of the parent node, left, and right child

    \begin{algorithm}
    \caption{Parent}
    \begin{algorithmic}
    \PROCEDURE{Parent}{$i$}
        \STATE{return $\lfloor(i / 2)\rfloor$}
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}

    \begin{algorithm}
    \caption{Left}
    \begin{algorithmic}
    \PROCEDURE{Left}{$i$}
        \STATE{return $2i$}
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}

    \begin{algorithm}
    \caption{Right}
    \begin{algorithmic}
    \PROCEDURE{Right}{$i$}
        \STATE{return $2i + 1$}
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}

There are two ways to implement the binary heaps, the max-heaps and min-heaps. Here we focus on the max-heap such that it obeys the max-heap property as follows

\[A[\text{Parent}(i)] \geq A[i]\]

• The \(\textbf{Max-Heapify}\) running time is \(O(log \: n)\) logarthimic time, which maintains the max-heap property.

• The \(\textbf{Build-Max-Heap}\) running time is \(O(n)\) linear time, builds a max-heap from an unordered input array.

• The \(\textbf{HeapSort}\) running time is \(O(n \: log \: n)\) which sorts the array in place.

    \begin{algorithm}
    \caption{Max-Heapify}
    \begin{algorithmic}
    \PROCEDURE{Max-Heapify}{$A, i$}
        \STATE{$l = $ \textsc{Left}$(i)$}
        \STATE{$r = $ \textsc{Right}$(i)$}
        \IF{$l \leq A$.heap-size and $A[l] > A[i]$}
            \STATE{largest $= l$}
        \ELSE
            \STATE{largest $= i$} 
        \ENDIF
        \IF{$r \leq A$.heap-size and $A[r] > A[largest]$}
            \STATE{$largest = r$}
        \ENDIF
        \IF{$largest \neq i$}
            \STATE{exchange $A[i]$ with $A[largest]$}
            \STATE \CALL{Max-Heapify}{$A, largest$}
        \ENDIF
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}

Building a heap

    \begin{algorithm}
    \caption{Build-Max-Heap}
    \begin{algorithmic}
    \PROCEDURE{Build-Max-Heap}{$A, n$}
        \STATE{$A.$heap-size = $n$}
        \FOR{ $i \gets \lfloor n / 2 \rfloor$ down to 1}
            \STATE \CALL{Max-Heapify}{$A, i$}
        \ENDFOR
    \ENDPROCEDURE
    \end{algorithmic}
    \end{algorithm}