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.