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

Algorithm 1 Parent

procedure Parent($i$)

return $\lfloor \left(i/2\right)\rfloor$

end procedure

Algorithm 2 Left

procedure Left($i$)

return $2i$

end procedure

Algorithm 3 Right

procedure Right($i$)

return $2i+1$

end procedure

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)]\ge A[i]$$

• The $\mathbf{\text{Max-Heapify}}$ running time is $O(logn)$ logarthimic time, which maintains the max-heap property.

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

• The $\mathbf{\text{HeapSort}}$ running time is $O(nlogn)$ which sorts the array in place.

Algorithm 4 Max-Heapify

procedure Max-Heapify($A,i$)

$l=$ Left$\left(i\right)$

$r=$ Right$\left(i\right)$

if $l\le A$.heap-size and $A\left[l\right]>A\left[i\right]$ then

largest $=l$

else

largest $=i$

end if

if $r\le A$.heap-size and $A\left[r\right]>A\left[largest\right]$ then

$largest=r$

end if

if $largest\ne i$ then

exchange $A\left[i\right]$ with $A\left[largest\right]$

Max-Heapify($A,largest$)

end if

end procedure

Building a heap

Algorithm 5 Build-Max-Heap

procedure Build-Max-Heap($A,n$)

$A.$heap-size = $n$

for $i\leftarrow \lfloor n/2\rfloor$ down to 1 do

Max-Heapify($A,i$)

end for

end procedure