From 68f5af63076e3b6e59829e95aa29567649b1e054 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 23 Apr 2008 19:20:34 +0200
Subject: [PATCH] A picture of a Q-heap.

---
 PLAN    | 16 ----------------
 ram.tex | 13 +++++++++++++
 2 files changed, 13 insertions(+), 16 deletions(-)

diff --git a/PLAN b/PLAN
index dfd8d68..8494170 100644
--- a/PLAN
+++ b/PLAN
@@ -48,18 +48,6 @@
 
 TODO:
 
-Preface:
-
-- mention notation
-- cite GA booklet
-- mention bugs in Valeria's verification paper
-
-- G has to be connected, so m=O(n)
-
-Spanning trees:
-
-- cite Eisner's tutorial \cite{eisner:tutorial}
-
 Applications:
 
 - K best trees
@@ -93,7 +81,3 @@ Global:
 
 - each chapter should make clear in which model we work
 - clean up bibliography
-
-Pictures:
-
-- structure of a Q-heap
diff --git a/ram.tex b/ram.tex
index 9cd8244..2517b2b 100644
--- a/ram.tex
+++ b/ram.tex
@@ -955,6 +955,19 @@ lengths of the strings in~$S$.
 For our set~$X$, we define~$T$ as a~compressed trie for the set of binary
 encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W \mid x\in X \}$.
 
+\float{\valign{\vfil#\vfil\cr
+\hbox{\epsfbox{pic/qheap.eps}}\cr
+\noalign{\qquad\quad}
+  \halign{#\hfil&\quad#\hfil\cr
+    $x_1 = \0\0\0\0\1\1$ & $g_1=3$ \cr
+    $x_2 = \0\0\1\0\1\0$ & $g_2=4$ \cr
+    $x_3 = \0\1\0\0\0\1$ & $g_3=2$ \cr
+    $x_4 = \0\1\0\1\0\1$ & $g_4=5$ \cr
+    $x_5 = \1\0\0\0\0\0$ & $g_5=0$ \cr
+    $x_6 = \1\0\0\0\0\1$ \cr
+  }\cr
+}}{Six numbers stored in a~compressed trie}
+
 \obs
 The trie~$T$ has several interesting properties. Since all words in~$S$ have the same
 length, the leaves of the trie correspond to these exact words, that is to the numbers~$x_i$.
-- 
2.39.2