In the previous post, I talked about heap data structure, a tree-based implementation in OCaml. This post will discuss how it is used to implement the heap sort algorithm. This sorting algorithm has worst-case time complexity.

## Algorithm

Assume that we want to sort the list `[4; 1; 5; 3; 2]`

in decreasing order. We assume further that the input list is represented by a complete binary min heap with 5 nodes as shown on the top of Figure 1.

To sort the list we create an empty list as the output list. We pick the key value `1`

of the heap’s root and put it into the output list. Then we remove the root `Node 1`

from the heap. After these actions, we get a new heap with the root is `Node 2`

and a new output list with one element `1`

. If we do the actions above until the heap is empty (e.g., represented by a node `Leaf`

), then we get the final output list is in decreasing order `[5; 4; 3; 2; 1]`

. The process is depicted in Figure 1. Thus the heap-sort algorithm can be divided into the following steps. The result list is initialized empty.

- Build a complete binary min heap from the input list
- Get the root of the heap and concatenate it with the result list
- Remove the root. If the heap is not empty, then goto step 2
- If the sorting direction is decreasing then return the result list, otherwise, return the reversed list

The heap building is time complexity. The getting and removing the root operations are and , respectively, and they are called times. Therefore, the time complexity of the heap-sort algorithm is .

## Code

This post demonstrates the use of extending modules with functor in OCaml programming language as well.
Let’s see how this works in the context of the `Heap`

module to add the additional functionality
for sorting. Instead of writing a heap-sort module extending the heap module with the sorting function by hand, we use a functor to add this functionality to the heap module that supports the `fold_on_min`

function.

We create a new module `Heapsort`

that automates the process of adding sorting function to the `Heap`

module. As you can see, `Heapsort`

contains a `type k`

of the `Heap`

key type, a function `sort_list`

to sort a list of this type, and a functor `Make`

that allows one to extend a `Heap`

module.

```
(************************************)
(* Heap-sort *)
(* Van Chan Ngo *)
(************************************)
(** Implementation of binary heap over ordered types *)
open Heap
type direction = Dec | Inc
module type Heapsort = sig
type k
val sort_list : direction -> k list -> k list
end
module Make (H : Heap) : (Heapsort with type k = H.key)
```

```
open Heap
type direction = Dec | Inc
module type Heapsort = sig
type k
val sort_list : direction -> k list -> k list
end
module Make (H : Heap) = struct
type k = H.key
let sort_list d l =
let h = H.of_list l in
let ol = H.fold_on_min (fun a k -> k::a) [] h in
match d with
| Dec -> ol
| Inc -> List.rev ol
end
```

In order to apply the functor, we create a heap module from a module `OrdertedType`

. For example, I want to sort a list of integer pairs, I first create a module `IntPair`

module. Then a heap module `H`

is created from `IntPair`

. Finally, a heap-sort module is created from `H`

using the functor.

```
open Heap
open Heapsort
module IntPair =
struct
type t = int * int
let to_string x =
let (x1,x2) = x in
"(" ^ (string_of_int x1) ^ "," ^ (string_of_int x2) ^ ")"
let compare (x1,y1) (x2,y2) =
if x1 > x2 then
Gt
else if x1 < x2 then
Lt
else
begin
if y1 > y2 then
Gt
else if y1 < y2 then
Lt
else
Eq
end
end
module H = Heap.Make(IntPair)
module HS = Heapsort.Make(H)
let _ =
let ol = HS.sort_list (Inc :direction) [(1,2); (2,3); (2,343223); (432332525,1333); (342395835289,29235899589); (248,35989835)] in
List.iter (fun (x,y) -> Printf.printf "(%d,%d) " x y) ol; Printf.printf "\n"
```

The sorted output list is

```
(1,2) (2,3) (2,343223) (248,35989835) (432332525,1333) (342395835289,29235899589)
```