From 5671402068c61ea159c82c725d6c5d8e7d0c2986 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 26 Mar 2008 13:33:40 +0100 Subject: [PATCH] More soft heaps. --- macros.tex | 12 +++++ opt.tex | 128 +++++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 121 insertions(+), 19 deletions(-) diff --git a/macros.tex b/macros.tex index 2ac7bbf..96be1cc 100644 --- a/macros.tex +++ b/macros.tex @@ -51,6 +51,8 @@ \def\poly{\mathop{\rm poly}} \def\E{{\bb E}} +\def\brk{\hfil\break} + % Bit strings \def\0{{\bf 0}} \def\1{{\bf 1}} @@ -409,6 +411,16 @@ \centerline{#3} \endinsert} +\def\multicap#1{ +\let\\=\break +\vbox{\hsize=0.7\hsize +\parindent=0pt +\leftskip=0pt plus 0.3\hsize +\rightskip=\leftskip +\parfillskip=0pt +#1 +}} + %%% Stand-alone chapters %%% \def\endpart{ diff --git a/opt.tex b/opt.tex index 7106858..5483027 100644 --- a/opt.tex +++ b/opt.tex @@ -36,33 +36,123 @@ supports the following operations: (optionally signalling that the value has been corrupted). \endlist -\figure{softheap1.eps}{\epsfxsize}{XXXX} - -\figure{softheap2.eps}{\epsfxsize}{XXXX} - \defnn{Soft queues} The soft heap is built from \df{soft queues} (we will omit the adjective soft in the rest of this section). Each queue has a~shape of a~binary tree.\foot{% Actually, Chazelle defines the queues as binomial trees, but he transforms them in ways that are somewhat counter-intuitive, albeit well-defined. We prefer describing the queues as binary -trees with a~special distribution of values. In fact, we get this exact type of binary -trees from the natural correspondence between general rooted trees and binary trees -(as described for example in Knuth's Fundamental Algorithms \cite{knuth:fundalg}). -Also, the original C~code in the Chazelle's paper uses this representation internally.} -Each vertex~$v$ of the tree remembers a~linked list $\(v)$ of values. The first value in the list -is called the \df{controlling key} of the vertex, denoted by $\(v)$ and defined to be~$+\infty$ if the -list is empty. The item list in every left son will be used only temporarily and it -will be kept empty between operations. Only right sons and the root have their lists -permanently occupied. (See the picture.) - -Each vertex is also assigned its \df{rank,} which is a~non-negative integer $\(v)$. +trees with a~special distribution of values. In fact, the original C~code in the Chazelle's +paper uses this representation internally.} +Each vertex~$v$ of the tree remembers a~linked list $\(v)$ of values. The +item list in every left son will be used only temporarily and it will be kept +empty between operations. Only right sons and the root have their lists +permanently occupied. The former vertices will be called \df{white}, the latter +\df{black.} (See the picture.) + +The first value in the list is called the \df{controlling key} of the vertex, +denoted by $\(v)$. If the list is empty, we keep the most recently used +value or we set $\(v)=+\infty$. The \'s obey the standard \df{heap order} +--- a~\ of a~parent is always less than the \'s of its sons. + +Each vertex is also assigned its \df{rank,} which is a~non-negative integer. The rank of leaves is always zero, the rank of every internal vertex must be strictly -greater than the ranks of its sons. +greater than the ranks of its sons. We define the rank of a~queue to be equal to the +rank of its root vertex and similarly for its \. + +A~queue is called \df{complete} if every two vertices joined by an~edge have rank +difference exactly one. In other words, it is a~complete binary tree and the +ranks correspond to vertex heights. + +\figure{softheap1.eps}{\epsfxsize}{\multicap{A~complete and a~partial soft queue tree\\ +(black vertices contain items, numbers indicate ranks)}} \obs -The rank of the root..... -Complete binary trees..... -The master tree..... +A~complete queue of rank~$k$ contains exactly~$2^{k+1}-1$ vertices, $2^k$~of which are +black (by induction). Any other queue can be trivially embedded to a~complete queue of the same +rank, which we will call the \df{master tree} of the queue. This embedding preserves vertex +ranks, colors and the ancestor relation. + +The queues have a~nice recursive structure. We can construct a~queue of rank~$k$ by \df{joining} +two queues of rank~$k-1$ under a~new root. The root will inherit the item list of one +of the original roots and also its \. To preserve the heap order, we will choose +the one whose \ is smaller. + +Sometimes, we will need to split a~queue to smaller queues. We will call this operation +\df{dismantling} the queue and it will happen only in cases when the item list in the root +is empty. It suffices to remove the leftmost (all white) path going from the root. From +a~queue of rank~$k$, we get queues of ranks $0,1,\ldots,k-1$, some of which may be missing +if the original queue was not complete. + +We will now combine the soft queues to the soft heap. + +\figure{softheap2.eps}{\epsfxsize}{Joining and dismantling soft queues} + +\defn A~\df{soft heap} consists of: +\itemize\ibull +\:a~doubly linked list of soft queues of distinct ranks (in increasing order of ranks), + we will call the first queue the \df{head}, the last queue will be its \df{tail}; +\:\df{suffix minima:} each queue contains a~pointer to the queue with minimum \ +of those following it in the list; +\:and a~global parameter~$r\in{\bb N}$, to be set depending on~$\varepsilon$. +\endlist +\>The heap always keeps the \df{Rank invariant:} When a~root of a~tree has rank~$k$, +its leftmost path has length at least~$k/2$. + +\para +\em{Melding} of two soft heaps involves merging of their lists of queues. We disassemble +the heap with the smaller maximum rank and we insert its queues to the other heap. +If two queues of the same rank~$k$ appear in both lists, we \em{join} them to +a~single queue of rank~$k+1$ as already described and we propagate the new queue as +a~\df{carry} to the next iteration, similarly to addition of binary numbers. +Finally we have to update the suffix minima by walking the new list backwards +from the last inserted item. + +\em{Creation} of a~new soft heap is trivial, \em{insertion} is handled by creating +a~single-element heap and melding it to the destination heap. + +\algn{Creating a~new soft heap} +\algo +\algin A~parameter~$\varepsilon$. +\:Allocate memory for a~new heap structure~$H$. +\:Initialize the list of queues in~$H$ as an~empty list. +\:Set the parameter~$r$ to~$2\lceil\log(1/\varepsilon)\rceil+2$ (to be justified later). +\algout A~newly minted soft heap~$H$. +\endalgo + +\algn{Melding of two soft heaps} +\algo +\algin Two soft heaps~$H_1$ and~$H_2$. +\:If the tail of~$H_1$ has smaller rank than the tail of~$H_2$, exchange $H_1$ and~$H_2$. +\brk\cmt{Whenever we run into an~end of a~list, we assume that it contains an~empty queue of infinite rank.} +\:$p\=\(H_1)$. +\:While $H_2$ still has some queues: +\::$q\=\(H_2)$. +\::If $\(p) < \(q)$, then $p\=$ the successor of~$p$, +\::else if $\(p) > \(q)$, remove~$q$ from~$H_2$ and insert it before~$p$, +\::otherwise (the ranks are equal, we need to propagate the carry): +\:::$\=p$. +\:::$p\=$ the successor of~$p$. +\:::While $\(q)=\(\)$: +\::::Remove~$q$ from~$H_2$. +\::::$\\=\(q, \)$. +\::::$q\=\(H_2)$. +\:::Insert~\ before~$q$. +\:Update the suffix minima: Walk with~$p$ backwards to the head of~$H_1$: +\::$p'\=$ successor of~$p$. +\::If $\(p) < \(p')$, set $\(p)\=p$. +\::Otherwise set $\(p)\=\(p')$. +\:Destroy the heap~$H_2$. +\algout The merged heap~$H_1$. +\endalgo + +\algn{Insertion of an~element to a~soft heap} +\algo +\algin A~heap~$H$ and a~new element~$x$. +\:Create a~new heap~$H'$ containing a~sole queue of rank~0, whose only vertex has + the element~$x$ in its item list. +\:$\(H,H')$. +\algout An~updated heap~$H$. +\endalgo \endpart -- 2.39.2