Introduction

Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure. It was first proposed by J. W. J. Williams in 1964. Heapsort is an in-place algorithm, meaning that it sorts the array in place, without needing any additional memory. It has a time complexity of O(n log n), which makes it efficient for large data sets.

Implementation

Here is an implementation of heapsort in OCaml:

let swap arr i j =
  let temp = arr.(i) in
  arr.(i) <- arr.(j);
  arr.(j) <- temp

let rec heapify arr n i =
  let largest = ref i in
  let left = 2 * i + 1 in
  let right = 2 * i + 2 in
  if left < n && arr.(left) > arr.(!largest) then
    largest := left;
  if right < n && arr.(right) > arr.(!largest) then
    largest := right;
  if !largest <> i then (
    swap arr i !largest;
    heapify arr n !largest
  )

let heapsort arr =
  let n = Array.length arr in
  for i = n / 2 - 1 downto 0 do
    heapify arr n i
  done;
  for i = n - 1 downto 1 do
    swap arr 0 i;
    heapify arr i 0
  done

Here is an example of how to use the heapsort function:

let arr = [|4; 2; 7; 1; 3|]
let () = heapsort arr
let () = Array.iter (Printf.printf "%d ") arr

Output:

1 2 3 4 7

Step-by-step Explanation

  1. Build a max heap from the input data. A binary heap is a complete binary tree where each node is greater than or equal to its children. The largest element is stored at the root of the heap.
  2. Swap the root node with the last element in the array. Decrease the heap size by 1.
  3. Call heapify on the root node to restore the heap property.
  4. Repeat steps 2-3 until the heap size is 1.

The heapify function takes three arguments: the array to be sorted, the size of the heap, and the index of the current node. It compares the current node with its left and right children and swaps it with the largest child if necessary. It then recursively calls heapify on the largest child to ensure that the subtree rooted at the current node is also a heap.

Complexity Analysis

The time complexity of heapsort is O(n log n) in the worst case. Building the heap takes O(n) time, and each call to heapify takes O(log n) time. We call heapify n-1 times in the second loop, so the total time complexity is O(n log n).

Heapsort is an in-place sorting algorithm, so it requires no additional memory beyond the array to be sorted. However, it is not a stable sorting algorithm, meaning that it does not preserve the relative order of equal elements in the input array.