5.7. Priority Queues¶
- File:
PriorityQueue.ml
Recall our main motivation for studying binary heaps: efficient retrieval of an element with maximal/minimal key in an array, without re-sorting it from scratch between the changes. A data structure that allows for efficient retrieval of an element with the highest/lowest key is called a priority queue. In this section, we will design a priority queue based on the implementation of the heaps we already have.
The priority queue will be implemented by a dedicated data type and a number of operations, all residing within the following functor:
module PriorityQueue(C: CompareAndPrint) = struct
(* To be filled *)
end
A carrier of a priority queue (i.e., a container for its elements) will be, of course, an array. Therefore, a priority queue may only hold as many elements as is the size of the array.
We introduce a small encoding tweak, which will be very helpful for
accounting for the fact that the array might be not fully filled,
allowing the priority queue to grow (as more elements are added to it)
and shrink (as the elements are extracted). Let us add the following
definitions into the body of PriorityQueue
:
module COpt = struct
type t = C.t option
let comp x y = match x, y with
| Some a, Some b -> C.comp a b
| None, Some _ -> -1
| Some _, None -> 1
| None, None -> 0
let pp x = match x with
| Some x -> C.pp x
| None -> "None"
end
module H = Heaps(COpt)
(* Do no inline, just include *)
open H
The module COpt
“lifts” the pretty-printer and the comparator of a
given module C
(of signature CompareAndPrint
), to the elements
of type option
. Specifically, if an element is None
, it is
strictly smaller than any Some
-like elements. As you can guess,
the None
elements will denote the “empty space” in our priority
queue.
5.7.1. Creating Priority Queues¶
The queue is represented by an OCaml record of the following shape (also to be added to the module):
type heap = {
heap_size : int ref;
arr : H.t array
}
The records in OCaml are similar to those in C and are simply collections of named values (referred to as record fields). Specifically, the record type heap
pairs the carrier array arr
of elements of type H.t
(i.e., C.t
lifted to an option), and the dedicated “heap threshold” heap_size
to determine which part of arr
serves as a heap.
The following two functions allow to create an empty priority queue of a given size, and also turn an array into a priority queue (by effectively building a heap out of it):
let mk_empty_queue size =
assert (size >= 0);
{heap_size = ref 0;
arr = Array.make size None}
(* Make a priority queue from an array *)
let mk_queue a =
let ls = List.map (fun e -> Some e) (to_list a) in
let a' = list_to_array ls in
build_max_heap a';
{heap_size = ref (Array.length a);
arr = a'}
Finally, the following construction allows to print out the contents of a priority queue by reusing the functor ArrayPrinter
defined at the beginning of this chapter:
module P = ArrayPrinter(COpt)
let print_heap h =
P.print_array h.arr
5.7.2. Operations on Priority Queues¶
The first and the simplest operation on a priority queue h
is to take its highest-ranked element (i.e., the one with the greatest priority, expressed by means of its key value):
let heap_maximum h = (h.arr).(0)
The next operation allows not just look at, but also extract (i.e., fetch and remove) the maximal element from the priority queue:
let heap_extract_max h =
if !(h.heap_size) < 1 then None
else
let a = h.arr in
let max = a.(0) in
a.(0) <- a.(!(h.heap_size) - 1);
a.(!(h.heap_size) - 1) <- None;
h.heap_size := !(h.heap_size) - 1;
max_heapify !(h.heap_size) h.arr 0;
max
The way heap_extract_max
works for a non-empty heap is by taking its maximal element, and then putting one of the smallest elements (a.(!(h.heap_size) - 1)
) to its place, reducing the heap size and restoring the heap shape via already familiar procedure max_heapify
applied to the first element in the array (which is the only heap offender after swapping).
The following auxiliary function heap_increase_key
is somewhat dual to max_heapify
. It inserts an element key
into a position i
, assuming that its key is larger than what’s currently at that position. It then restores the heap property (which might be broken if the parents in the chain are smaller) by “walking up” the chain of parents and performing swaps until the correct order is restored:
let heap_increase_key h i key =
let a = h.arr in
let c = comp key (a.(i)) >= 0 in
if not c then (
Printf.printf "A new key is smaller than current key!";
assert false);
a.(i) <- key;
let j = ref i in
while !j > 0 && comp (snd (H.parent a (!j))) a.(!j) < 0 do
let pj = fst (H.parent a (!j)) in
swap a !j pj;
j := pj
done
Question: What is the complexity of heap_increase_key
?
Finally, the function max_heap_insert
implements an insertion of a
new element elem
into a priority heap h
:
let max_heap_insert h elem =
let hs = !(h.heap_size) in
if hs >= Array.length h.arr
then raise (Failure "Maximal heap capacity reached!");
h.heap_size := hs + 1;
heap_increase_key h hs (Some elem)
It only succeeds in the case if there is still vacant space in the
queue (i.e., at the end of the array), which can be determined by
examining the heap_size
field of h
. If the space permits, the
limit heap_size
is increased. Since we know that None
used to
be installed to the vacant place (which is an invariant maintained by
means of heap_size
), we can simply install the new element Some
elem
(which is guaranteed to be larger than None
as per our
defined comparator) and let the heap rebalance using
heap_increase_key
.
Given the complexity of max_heap_insert
, it is easy to show that
the complexity of element insertion is \(O(\log n)\). This brings
us to an important property of priority queues implemented by means of
heaps:
Complexity of priority queue operations
For a priority queue of size \(n\),
- Finding the largest element has complexity \(O(1)\),
- Extraction of the largest element has complexity \(O(\log n)\),
- Insertion of a new element has complexity \(O(\log n)\).
5.7.3. Working with Priority Queues¶
Let us see a priority queue in action. We start by creating it from a randomly generated array:
module PQ = PriorityQueue(KV)
open PQ
let q = mk_queue (
[|(6, "egkbs"); (4, "nugab"); (4, "xcwjg");
(4, "oxfyr"); (4, "opdhq"); (0, "huiuv");
(0, "sbcnl"); (2, "gzpyp"); (4, "hymnz");
(2, "yxzro")|]);;
Let us see what’s inside:
# q;;
- : PQ.heap =
{heap_size = {contents = 10};
arr =
[|Some (6, "egkbs"); Some (4, "nugab"); Some (4, "xcwjg");
Some (4, "oxfyr"); Some (4, "opdhq"); Some (0, "huiuv");
Some (0, "sbcnl"); Some (2, "gzpyp"); Some (4, "hymnz");
Some (2, "yxzro")|]}
We can proceed by checking the maximum:
# heap_maximum q;;
- : PQ.H.t = Some (6, "egkbs")
(* It is indeed a heap! *)
# PQ.H.is_heap q.arr;;
- : bool = true
Let us extract several maximum elements:
# heap_extract_max q;;
- : PQ.H.t option = Some (6, "egkbs")
# heap_extract_max q;;
- : PQ.H.t option = Some (4, "nugab")
# heap_extract_max q;;
- : PQ.H.t option = Some (4, "oxfyr")
# heap_extract_max q;;
- : PQ.H.t option = Some (4, "hymnz")
Is it still a heap?:
# q;;
- : PQ.heap =
{heap_size = {contents = 6};
arr =
[|Some (4, "opdhq"); Some (2, "yxzro"); Some (4, "xcwjg");
Some (0, "sbcnl"); Some (2, "gzpyp"); Some (0, "huiuv");
None; None; None; None|]}
# PQ.H.is_heap q.arr;;
- : bool = true
Finally, let us insert a new element and check whether it is still a heap:
# max_heap_insert q (7, "abcde");;
- : unit = ()
# q;;
- : PQ.heap =
{heap_size = {contents = 7};
arr =
[|Some (7, "abcde"); Some (2, "yxzro"); Some (4, "opdhq");
Some (0, "sbcnl"); Some (2, "gzpyp"); Some (0, "huiuv");
Some (4, "xcwjg"); None; None; None|]}
# heap_maximum q;;
- : PQ.H.t = Some (7, "abcde")