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> <pbewigF0A81I.Ipp@netcom.com> <6vj3ea$jhv$1@nnrp1.dejanews.com> <pbewigF0J787.HBJ@netcom.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.