author  nipkow 
Wed, 25 Sep 2019 17:22:57 +0200  
changeset 70944  3fb16bed5d6c 
parent 70771  eecade21bc6a 
child 72513  415220b59d37 
permissions  rwrr 
62706  1 
(* Author: Tobias Nipkow *) 
2 

3 
section \<open>Leftist Heap\<close> 

4 

5 
theory Leftist_Heap 

66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

6 
imports 
70636  7 
"HOLLibrary.Pattern_Aliases" 
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

8 
Tree2 
68493  9 
Priority_Queue_Specs 
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

10 
Complex_Main 
62706  11 
begin 
12 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

13 
fun mset_tree :: "('a*'b) tree \<Rightarrow> 'a multiset" where 
64969  14 
"mset_tree Leaf = {#}"  
70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

15 
"mset_tree (Node l (a, _) r) = {#a#} + mset_tree l + mset_tree r" 
64969  16 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

17 
type_synonym 'a lheap = "('a*nat)tree" 
62706  18 

19 
fun rank :: "'a lheap \<Rightarrow> nat" where 

20 
"rank Leaf = 0"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

21 
"rank (Node _ _ r) = rank r + 1" 
62706  22 

23 
fun rk :: "'a lheap \<Rightarrow> nat" where 

24 
"rk Leaf = 0"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

25 
"rk (Node _ (_, n) _) = n" 
62706  26 

67406  27 
text\<open>The invariants:\<close> 
64969  28 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

29 
fun (in linorder) heap :: "('a*'b) tree \<Rightarrow> bool" where 
64969  30 
"heap Leaf = True"  
70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

31 
"heap (Node l (m, _) r) = 
70771  32 
(heap l \<and> heap r \<and> (\<forall>x \<in> set_tree l \<union> set_tree r. m \<le> x))" 
62706  33 

64973  34 
fun ltree :: "'a lheap \<Rightarrow> bool" where 
35 
"ltree Leaf = True"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

36 
"ltree (Node l (a, n) r) = 
64973  37 
(n = rank r + 1 \<and> rank l \<ge> rank r \<and> ltree l & ltree r)" 
62706  38 

70771  39 
definition empty :: "'a lheap" where 
40 
"empty = Leaf" 

41 

62706  42 
definition node :: "'a lheap \<Rightarrow> 'a \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where 
43 
"node l a r = 

44 
(let rl = rk l; rr = rk r 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

45 
in if rl \<ge> rr then Node l (a,rr+1) r else Node r (a,rl+1) l)" 
62706  46 

47 
fun get_min :: "'a lheap \<Rightarrow> 'a" where 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

48 
"get_min(Node l (a, n) r) = a" 
62706  49 

66502  50 
text \<open>For function \<open>merge\<close>:\<close> 
51 
unbundle pattern_aliases 

66492  52 

66502  53 
fun merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where 
70771  54 
"merge Leaf t = t"  
55 
"merge t Leaf = t"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

56 
"merge (Node l1 (a1, n1) r1 =: t1) (Node l2 (a2, n2) r2 =: t2) = 
66492  57 
(if a1 \<le> a2 then node l1 a1 (merge r1 t2) 
68600  58 
else node l2 a2 (merge t1 r2))" 
62706  59 

70771  60 
text \<open>Termination of @{const merge}: by sum or lexicographic product of the sizes 
61 
of the two arguments. Isabelle uses a lexicographic product.\<close> 

62 

64976  63 
lemma merge_code: "merge t1 t2 = (case (t1,t2) of 
62706  64 
(Leaf, _) \<Rightarrow> t2  
65 
(_, Leaf) \<Rightarrow> t1  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

66 
(Node l1 (a1, n1) r1, Node l2 (a2, n2) r2) \<Rightarrow> 
68600  67 
if a1 \<le> a2 then node l1 a1 (merge r1 t2) else node l2 a2 (merge t1 r2))" 
64976  68 
by(induction t1 t2 rule: merge.induct) (simp_all split: tree.split) 
62706  69 

66524  70 
hide_const (open) insert 
71 

62706  72 
definition insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where 
70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

73 
"insert x t = merge (Node Leaf (x,1) Leaf) t" 
62706  74 

68021  75 
fun del_min :: "'a::ord lheap \<Rightarrow> 'a lheap" where 
76 
"del_min Leaf = Leaf"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

77 
"del_min (Node l _ r) = merge l r" 
62706  78 

79 

80 
subsection "Lemmas" 

81 

66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

82 
lemma mset_tree_empty: "mset_tree t = {#} \<longleftrightarrow> t = Leaf" 
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

83 
by(cases t) auto 
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

84 

64973  85 
lemma rk_eq_rank[simp]: "ltree t \<Longrightarrow> rk t = rank t" 
62706  86 
by(cases t) auto 
87 

64973  88 
lemma ltree_node: "ltree (node l a r) \<longleftrightarrow> ltree l \<and> ltree r" 
62706  89 
by(auto simp add: node_def) 
90 

64969  91 
lemma heap_node: "heap (node l a r) \<longleftrightarrow> 
70771  92 
heap l \<and> heap r \<and> (\<forall>x \<in> set_tree l \<union> set_tree r. a \<le> x)" 
64969  93 
by(auto simp add: node_def) 
94 

70771  95 
lemma set_tree_mset: "set_tree t = set_mset(mset_tree t)" 
96 
by(induction t) auto 

62706  97 

98 
subsection "Functional Correctness" 

99 

64976  100 
lemma mset_merge: "mset_tree (merge h1 h2) = mset_tree h1 + mset_tree h2" 
101 
by (induction h1 h2 rule: merge.induct) (auto simp add: node_def ac_simps) 

62706  102 

64969  103 
lemma mset_insert: "mset_tree (insert x t) = mset_tree t + {#x#}" 
64976  104 
by (auto simp add: insert_def mset_merge) 
62706  105 

70771  106 
lemma get_min: "\<lbrakk> heap h; h \<noteq> Leaf \<rbrakk> \<Longrightarrow> get_min h = Min(set_tree h)" 
66424  107 
by (induction h) (auto simp add: eq_Min_iff) 
64969  108 

68021  109 
lemma mset_del_min: "mset_tree (del_min h) = mset_tree h  {# get_min h #}" 
64976  110 
by (cases h) (auto simp: mset_merge) 
62706  111 

64976  112 
lemma ltree_merge: "\<lbrakk> ltree l; ltree r \<rbrakk> \<Longrightarrow> ltree (merge l r)" 
113 
proof(induction l r rule: merge.induct) 

68414  114 
case (3 l1 a1 n1 r1 l2 a2 n2 r2) 
64976  115 
show ?case (is "ltree(merge ?t1 ?t2)") 
62706  116 
proof cases 
117 
assume "a1 \<le> a2" 

64976  118 
hence "ltree (merge ?t1 ?t2) = ltree (node l1 a1 (merge r1 ?t2))" by simp 
119 
also have "\<dots> = (ltree l1 \<and> ltree(merge r1 ?t2))" 

64973  120 
by(simp add: ltree_node) 
67406  121 
also have "..." using "3.prems" "3.IH"(1)[OF \<open>a1 \<le> a2\<close>] by (simp) 
62706  122 
finally show ?thesis . 
123 
next (* analogous but automatic *) 

124 
assume "\<not> a1 \<le> a2" 

64973  125 
thus ?thesis using 3 by(simp)(auto simp: ltree_node) 
62706  126 
qed 
127 
qed simp_all 

128 

64976  129 
lemma heap_merge: "\<lbrakk> heap l; heap r \<rbrakk> \<Longrightarrow> heap (merge l r)" 
130 
proof(induction l r rule: merge.induct) 

70771  131 
case 3 thus ?case by(auto simp: heap_node mset_merge ball_Un set_tree_mset) 
64969  132 
qed simp_all 
133 

64973  134 
lemma ltree_insert: "ltree t \<Longrightarrow> ltree(insert x t)" 
64976  135 
by(simp add: insert_def ltree_merge del: merge.simps split: tree.split) 
62706  136 

64969  137 
lemma heap_insert: "heap t \<Longrightarrow> heap(insert x t)" 
64976  138 
by(simp add: insert_def heap_merge del: merge.simps split: tree.split) 
64969  139 

68021  140 
lemma ltree_del_min: "ltree t \<Longrightarrow> ltree(del_min t)" 
64976  141 
by(cases t)(auto simp add: ltree_merge simp del: merge.simps) 
62706  142 

68021  143 
lemma heap_del_min: "heap t \<Longrightarrow> heap(del_min t)" 
64976  144 
by(cases t)(auto simp add: heap_merge simp del: merge.simps) 
64969  145 

66564  146 
text \<open>Last step of functional correctness proof: combine all the above lemmas 
147 
to show that leftist heaps satisfy the specification of priority queues with merge.\<close> 

62706  148 

66564  149 
interpretation lheap: Priority_Queue_Merge 
70771  150 
where empty = empty and is_empty = "\<lambda>h. h = Leaf" 
68021  151 
and insert = insert and del_min = del_min 
66564  152 
and get_min = get_min and merge = merge 
153 
and invar = "\<lambda>h. heap h \<and> ltree h" and mset = mset_tree 

62706  154 
proof(standard, goal_cases) 
70771  155 
case 1 show ?case by (simp add: empty_def) 
62706  156 
next 
64975  157 
case (2 q) show ?case by (cases q) auto 
62706  158 
next 
64975  159 
case 3 show ?case by(rule mset_insert) 
160 
next 

68021  161 
case 4 show ?case by(rule mset_del_min) 
62706  162 
next 
70771  163 
case 5 thus ?case by(simp add: get_min mset_tree_empty set_tree_mset) 
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

164 
next 
70771  165 
case 6 thus ?case by(simp add: empty_def) 
62706  166 
next 
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

167 
case 7 thus ?case by(simp add: heap_insert ltree_insert) 
64969  168 
next 
68021  169 
case 8 thus ?case by(simp add: heap_del_min ltree_del_min) 
66564  170 
next 
171 
case 9 thus ?case by (simp add: mset_merge) 

172 
next 

173 
case 10 thus ?case by (simp add: heap_merge ltree_merge) 

62706  174 
qed 
175 

176 

177 
subsection "Complexity" 

178 

64973  179 
lemma pow2_rank_size1: "ltree t \<Longrightarrow> 2 ^ rank t \<le> size1 t" 
70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

180 
proof(induction t rule: tree2_induct) 
62706  181 
case Leaf show ?case by simp 
182 
next 

68414  183 
case (Node l a n r) 
62706  184 
hence "rank r \<le> rank l" by simp 
185 
hence *: "(2::nat) ^ rank r \<le> 2 ^ rank l" by simp 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

186 
have "(2::nat) ^ rank \<langle>l, (a, n), r\<rangle> = 2 ^ rank r + 2 ^ rank r" 
62706  187 
by(simp add: mult_2) 
188 
also have "\<dots> \<le> size1 l + size1 r" 

189 
using Node * by (simp del: power_increasing_iff) 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

190 
also have "\<dots> = size1 \<langle>l, (a, n), r\<rangle>" by simp 
62706  191 
finally show ?case . 
192 
qed 

193 

66492  194 
text\<open>Explicit termination argument: sum of sizes\<close> 
195 

66502  196 
fun t_merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> nat" where 
70771  197 
"t_merge Leaf t = 1"  
198 
"t_merge t Leaf = 1"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

199 
"t_merge (Node l1 (a1, n1) r1 =: t1) (Node l2 (a2, n2) r2 =: t2) = 
66492  200 
(if a1 \<le> a2 then 1 + t_merge r1 t2 
68600  201 
else 1 + t_merge t1 r2)" 
62706  202 

203 
definition t_insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> nat" where 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

204 
"t_insert x t = t_merge (Node Leaf (x, 1) Leaf) t" 
62706  205 

68021  206 
fun t_del_min :: "'a::ord lheap \<Rightarrow> nat" where 
207 
"t_del_min Leaf = 1"  

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

208 
"t_del_min (Node l _ r) = t_merge l r" 
62706  209 

64976  210 
lemma t_merge_rank: "t_merge l r \<le> rank l + rank r + 1" 
211 
proof(induction l r rule: merge.induct) 

68600  212 
case 3 thus ?case by(simp) 
62706  213 
qed simp_all 
214 

64976  215 
corollary t_merge_log: assumes "ltree l" "ltree r" 
216 
shows "t_merge l r \<le> log 2 (size1 l) + log 2 (size1 r) + 1" 

62706  217 
using le_log2_of_power[OF pow2_rank_size1[OF assms(1)]] 
64976  218 
le_log2_of_power[OF pow2_rank_size1[OF assms(2)]] t_merge_rank[of l r] 
62706  219 
by linarith 
220 

64973  221 
corollary t_insert_log: "ltree t \<Longrightarrow> t_insert x t \<le> log 2 (size1 t) + 2" 
70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

222 
using t_merge_log[of "Node Leaf (x, 1) Leaf" t] 
62706  223 
by(simp add: t_insert_def split: tree.split) 
224 

66492  225 
(* FIXME mv ? *) 
62706  226 
lemma ld_ld_1_less: 
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

227 
assumes "x > 0" "y > 0" shows "log 2 x + log 2 y + 1 < 2 * log 2 (x+y)" 
62706  228 
proof  
66422
8194ed7cf2cb
separate file for priority queue interface; extended Leftist_Heap.
nipkow
parents:
64977
diff
changeset

229 
have "2 powr (log 2 x + log 2 y + 1) = 2*x*y" 
64977  230 
using assms by(simp add: powr_add) 
231 
also have "\<dots> < (x+y)^2" using assms 

62706  232 
by(simp add: numeral_eq_Suc algebra_simps add_pos_pos) 
64977  233 
also have "\<dots> = 2 powr (2 * log 2 (x+y))" 
66492  234 
using assms by(simp add: powr_add log_powr[symmetric]) 
64977  235 
finally show ?thesis by simp 
62706  236 
qed 
237 

68021  238 
corollary t_del_min_log: assumes "ltree t" 
239 
shows "t_del_min t \<le> 2 * log 2 (size1 t) + 1" 

70944
3fb16bed5d6c
replaced new type ('a,'b) tree by old type ('a*'b) tree.
nipkow
parents:
70771
diff
changeset

240 
proof(cases t rule: tree2_cases) 
62706  241 
case Leaf thus ?thesis using assms by simp 
242 
next 

68414  243 
case [simp]: (Node t1 _ _ t2) 
68021  244 
have "t_del_min t = t_merge t1 t2" by simp 
62706  245 
also have "\<dots> \<le> log 2 (size1 t1) + log 2 (size1 t2) + 1" 
64976  246 
using \<open>ltree t\<close> by (auto simp: t_merge_log simp del: t_merge.simps) 
62706  247 
also have "\<dots> \<le> 2 * log 2 (size1 t) + 1" 
248 
using ld_ld_1_less[of "size1 t1" "size1 t2"] by (simp) 

249 
finally show ?thesis . 

250 
qed 

251 

252 
end 