Hello everybody:
I tried to implement a "pairing heap" with all the regular operations (merge, delete-min etc.), then I've been requested to write a function that would sort a list using my newly constructed heap implementation. Unfortunately it seems that someting goes wrong...
Here's the relevant code:
(define (heap-merge h1 h2)
(cond ((heap-empty? h1) h2)
((heap-empty? h2) h1)
(else (let ((min1 (heap-get-min h1))
(min2 (heap-get-min h2)))
(if ((heap-get-less h1) min1 min2)
(make-pairing-heap (heap-get-less h1) min1 (cons h2 (heap-get-subheaps h1)))
(make-pairing-heap (heap-get-less h1) min2 (cons h1 (heap-get-subheaps h2))))))))
(define (heap-insert element h)
(heap-merge (make-pairing-heap (heap-get-less h) element '())
h))
(define (heap-delete-min h)
(define (merge-in-pairs less? subheaps)
(cond
((null? subheaps) (make-heap less?))
((null? (cdr subheaps)) (car subheaps))
(else (heap-merge (heap-merge (car subheaps) (cadr subheaps))
(merge-in-pairs less? (cddr subheaps))))))
(if (heap-empty? h) (error "expected pairing-heap for first argument, got an empty heap ")
(merge-in-pairs (heap-get-less h) (heap-get-subheaps h))))
(define (heapsort l less?)
(let aux ((h (accumulate heap-insert (make-heap less?) l)))
(if (not (heap-empty? h))
(cons (heap-get-min h)
(aux (heap-delete-min h))))))
And these are some selectors that may help you to understand the code:
(define (make-pairing-heap less? min subheaps)
(cons less? (cons min subheaps)))
(define (make-heap less?)
(cons less? '()))
(define (heap-get-less h)
(car h))
(define (heap-empty? h)
(if (null? (cdr h)) #t #f))
Now lets get to the problem: When i run 'heapsort' it returns the sorted list with "void", as you can see: (heapsort (list 1 2 3) <)
(1 2 3 . #)..HOW CAN I FIX IT?
Regards,
Superguay
