From oleg@pobox.com Mon Oct 12 16:51:21 1998
Message-Id: <199810122351.SAA12961@x13.dejanews.com>
From: oleg-at-pobox.com
Subject: Can one prove complexity of priority queues?
Date: Mon, 12 Oct 1998 23:51:39 GMT
Keywords: algorithm analysis, skew heap, priority queue, complexity, Scheme
Newsgroups: comp.lang.scheme
Organization: Deja News - The Leader in Internet Discussion
References: <874stlqfue.fsf@ivm.de> <6vj3ea$jhv$1@nnrp1.dejanews.com>
Summary: complexity analysis of a particular priority queue implementation
X-Article-Creation-Date: Mon Oct 12 23:51:39 1998 GMT
X-Http-User-Agent: Mozilla/4.07 (Macintosh; I; PPC, Nav)
Status: RO
In his reply on Oct 8, Phil Bewig wrote:
> My priority queues use skew heaps, invented by Sleator and Tarjan (I
> don't have the reference handy, but I'll find it if necessary), with a
> total time of n log n for any n consecutive inserts and deletes. The
> code is so simple it *looks* like linear time, but any single
> operation is actually amortized logarithmic time.
I will attempt to dispute this statement. I will try to prove that in
one _particular_ case, an insertion in Phil Bewig's priority queue
takes linear amount of time and stack space. There is no
ammortization. Thus a sequence of these particular inserts would be
quadratic in time.
Let me first quote three functions from Phil Bewig's original message
that are relevant to the present discussion.
(define priqueue-nil '())
(define priqueue-merge
(lambda (pq-left pq-right)
(cond
((null? pq-left) pq-right)
((null? pq-right) pq-left)
((< (car pq-left) (car pq-right))
(list (car pq-left) pq-right
(priqueue-merge (cadr pq-left) (caddr pq-left))))
((null? (cadr pq-right))
(list (car pq-right) pq-left (caddr pq-right)))
(else
(list (car pq-right) (cadr pq-right)
(priqueue-merge pq-left (caddr pq-right)))))))
(define priqueue-insert
(lambda (k pq)
(priqueue-merge (list k priqueue-nil priqueue-nil) pq)))
Now to my contention.
Definitions.
(define (PQ k)
(if (zero? k) priqueue-nil
(priqueue-insert k (PQ (- k 1)))))
(define (PQ-map f pq)
(if (null? pq) '()
(list (f (car pq)) (PQ-map f (cadr pq)) (PQ-map f (caddr pq)))))
(define (plus2 x) (+ x 2))
Theorem:
Part A: (PQ n)
has the structure
1
2 3
4 5
6 7
(n-1) n
for n odd, and similar (without the rightmost leaf) for n even.
In other words,
(PQ n) = (list 1 '(2 () ()) (PQ-map plus2 (PQ (- n 2))), n>2
(PQ 1) = '(1 () ())
(PQ 2) = '(1 (2 () ()) ())
Part B: If pqn is bound to (PQ n), then
(priqueue-insert (+ n 1) pqn) requires floor(n/2)+1 nested evaluations
of priqueue-merge.
Proof. Base case:
(PQ 3) => (1 (2 () ()) (3 () ()))
or (list 1 '(2 () ()) (PQ-map plus2 (PQ 1)))
(PQ 4) => (1 (2 () ()) (3 (4 () ()) ()))
or (list 1 '(2 () ()) (PQ-map plus2 (PQ 2)))
(priqueue-insert 2 (PQ 1)) takes 1 evaluation of priqueue-merge
(priqueue-insert 3 (PQ 2)) takes 2 evaluations of
priqueue-merge
(not counting the ones needed to compute (PQ 2) itself)
Induction hypothesis. Let's assume the theorem holds for some
k>=3. That is, the queue has the following format:
(PQ k) = (list 1 '(2 () ()) (PQ-map plus2 (PQ (- k 2)))
Consider inserting element (k+1). By definition of priqueue-insert,
this results in
(priqueue-merge (list (+ k 1) '() '()) (PQ k)))
On entering this priqueue-merge:
pq-left is (list (+ k 1) '() '())
pq-right is (PQ k)
Note, that (car pq-left) is (+ k 1), and (car pq-right) is 1.
Also, (cadr pq-right) is '(2 () ()), which is not-nil. Thus, the
'else' clause of the priqueue-merge will be executed, which will
return
(list 1 '(2 () ())
(priqueue-merge (list (+ k 1) '() '()) (caddr pq-right)))
or, in other words
(list 1 '(2 () ()) (priqueue-insert (+ k 1) (caddr pq-right)))
Keeping in mind that pq-right is (PQ k) and applying the inductive
hypothesis we can rewrite the latter expression as
(list 1 '(2 () ()) (priqueue-insert (+ k 1) (PQ-map plus2 (PQ (- k 2)))))
Thus, priqueue-merge (or priqueue-insert, for that matter) would be
entered once again.
Operators PQ-map and priqueue-insert/priqueue-merge obviously
commute, therefore, the result of the latter priqueue-insert is
(PQ-map plus2 (priqueue-insert (- k 1) (PQ (- k 2))))
By definition of PQ, (priqueue-insert (- k 1) (PQ (- k 2))) is
(PQ (- k 1)). Thus,
(PQ (+ k 1)) which is (priqueue-insert (+ k 1) (PQ k))
turns out to be
(list 1 '(2 () ()) (PQ-map plus2 (PQ (- k 1))))
QED.
Part B: Time complexity: As shown above, (priqueue-insert (+ k 1) (PQ
k)) calls priqueue-merge, which returns
(list 1 '(2 () ())
(priqueue-merge (list (+ k 1) '() '()) (caddr pq-right)))
which requires more evaluations of priqueue-merge in a _non_-tail
recursive position. As shown above, the latter number is the same as the
number of priqueue-merge evaluations in computing of
(priqueue-insert (- k 1) (PQ (- k 2)))
which is floor((k-2)/2) + 1 by the induction hypothesis. Thus
(priqueue-insert (+ k 1) (PQ k))
requires 1 + floor((k-2)/2) +1 = floor(k/2) + 1 nested evaluations of
priqueue-merge. QED.