From 89c2cfcb9705555988fd011d56f3a6fad73652ed Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 5 Apr 2009 16:45:47 +0200 Subject: [PATCH] In the definiton of the soft queue, we should better explicitly mention that both sons always keep the same rank. --- opt.tex | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/opt.tex b/opt.tex index 067ac93..202e52b 100644 --- a/opt.tex +++ b/opt.tex @@ -96,9 +96,10 @@ value or we set $\(v)=+\infty$. The \s obey the standard \df{heap or Each vertex is also assigned its \df{rank,} which is a~non-negative integer. The ranks of leaves are always zero, the rank of every internal vertex can be -arbitrary, but it must be strictly greater than the ranks of its sons. We -define the rank of the whole queue to be equal to the rank of its root vertex and -similarly for its \. +arbitrary, but it must be strictly greater than the ranks of its sons. Also, +we will always maintain the ranks in such a~way that both sons will have the +equal ranks. We define the rank of the whole 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 -- 2.39.2