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 \(O(nlogn)\) worst-case time complexity.
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 \(O(nlogn)\) time complexity. The getting and removing the root operations are \(O(1)\) and \(O(logn)\), respectively, and they are called \(n\) times. Therefore, the time complexity of the heap-sort algorithm is \(O(nlogn)\).
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
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-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)