author | paulson |
Fri, 19 Mar 2004 10:42:38 +0100 | |
changeset 14472 | cba7c0a3ffb3 |
parent 9413 | ba209591a8d4 |
child 14981 | e73f8140af78 |
permissions | -rw-r--r-- |
9413 | 1 |
(* Title: Pure/General/heap.ML |
9095 | 2 |
ID: $Id$ |
9413 | 3 |
Author: Markus Wenzel, TU Muenchen |
4 |
License: GPL (GNU GENERAL PUBLIC LICENSE) |
|
9095 | 5 |
|
9413 | 6 |
Heaps over linearly ordered types. See also Chris Okasaki: "Purely |
7 |
Functional Data Structures" (Chapter 3), Cambridge University Press, |
|
8 |
1998. |
|
9 |
*) |
|
9095 | 10 |
|
11 |
signature HEAP = |
|
12 |
sig |
|
9413 | 13 |
type elem |
14 |
type T |
|
15 |
val empty: T |
|
16 |
val is_empty: T -> bool |
|
17 |
val merge: T * T -> T |
|
18 |
val insert: elem * T -> T |
|
19 |
exception EMPTY |
|
20 |
val min: T -> elem (*exception EMPTY*) |
|
21 |
val delete_min: T -> T (*exception EMPTY*) |
|
9095 | 22 |
end; |
23 |
||
9413 | 24 |
functor HeapFun(type elem val ord: elem * elem -> order): HEAP = |
9095 | 25 |
struct |
9413 | 26 |
|
27 |
||
28 |
(* datatype heap *) |
|
9095 | 29 |
|
9413 | 30 |
type elem = elem; |
31 |
datatype T = Empty | Heap of int * elem * T * T; |
|
32 |
||
33 |
||
34 |
(* empty heaps *) |
|
9095 | 35 |
|
9413 | 36 |
val empty = Empty; |
37 |
||
38 |
fun is_empty Empty = true |
|
39 |
| is_empty (Heap _) = false; |
|
40 |
||
9095 | 41 |
|
9413 | 42 |
(* build heaps *) |
43 |
||
44 |
local |
|
45 |
||
46 |
fun rank Empty = 0 |
|
47 |
| rank (Heap (r, _, _, _)) = r; |
|
9095 | 48 |
|
9413 | 49 |
fun heap x a b = |
50 |
if rank a >= rank b then Heap (rank b + 1, x, a, b) |
|
51 |
else Heap (rank a + 1, x, b, a); |
|
52 |
||
53 |
in |
|
54 |
||
55 |
fun merge (h, Empty) = h |
|
56 |
| merge (Empty, h) = h |
|
57 |
| merge (h1 as Heap (_, x1, a1, b1), h2 as Heap (_, x2, a2, b2)) = |
|
58 |
(case ord (x1, x2) of |
|
14472
cba7c0a3ffb3
Removing the datatype declaration of "order" allows the standard General.order
paulson
parents:
9413
diff
changeset
|
59 |
GREATER => heap x2 a2 (merge (h1, b2)) |
9413 | 60 |
| _ => heap x1 a1 (merge (b1, h2))); |
61 |
||
62 |
fun insert (x, h) = merge (Heap (1, x, Empty, Empty), h); |
|
9095 | 63 |
|
9413 | 64 |
end; |
65 |
||
66 |
||
67 |
(* minimum element *) |
|
68 |
||
69 |
exception EMPTY |
|
9095 | 70 |
|
9413 | 71 |
fun min Empty = raise EMPTY |
72 |
| min (Heap (_, x, _, _)) = x; |
|
73 |
||
74 |
fun delete_min Empty = raise EMPTY |
|
75 |
| delete_min (Heap (_, _, a, b)) = merge (a, b); |
|
76 |
||
9095 | 77 |
end; |