[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/YZIkmZ02    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Sep 25: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

; maxiphobic heaps

(define mh-node vector) ; size item lkid rkid

(define-syntax mh-size (syntax-rules () ((_ mh) (vector-ref mh 0))))
(define-syntax mh-item (syntax-rules () ((_ mh) (vector-ref mh 1))))
(define-syntax mh-lkid (syntax-rules () ((_ mh) (vector-ref mh 2))))
(define-syntax mh-rkid (syntax-rules () ((_ mh) (vector-ref mh 3))))

(define mh-empty (mh-node 0 'mh-empty 'mh-empty 'mh-empty))
(define (mh-empty? mh) (eqv? mh mh-empty))

(define (mh-merge lt? mh1 mh2)
  (cond ((mh-empty? mh1) mh2) ((mh-empty? mh2) mh1)
  (else (if (lt? (mh-item mh1) (mh-item mh2))
            (let ((mhs (mh-biggest (mh-lkid mh1) (mh-rkid mh1) mh2)))
              (mh-node (+ (mh-size mh1) (mh-size mh2))
                       (mh-item mh1) (car mhs)
                       (apply mh-merge lt? (cdr mhs))))
            (let ((mhs (mh-biggest mh1 (mh-lkid mh2) (mh-rkid mh2))))
              (mh-node (+ (mh-size mh1) (mh-size mh2))
                       (mh-item mh2) (car mhs)
                       (apply mh-merge lt? (cdr mhs))))))))

(define (mh-biggest mh1 mh2 mh3)
  (if (< (mh-size mh1) (mh-size mh2))
         (if (< (mh-size mh2) (mh-size mh3))
             (list mh3 mh1 mh2)
             (list mh2 mh1 mh3))
         (if (< (mh-size mh1) (mh-size mh3))
             (list mh3 mh1 mh2)
             (list mh1 mh2 mh3))))

(define (mh-insert lt? x mh)
  (mh-merge lt? (mh-node 1 x mh-empty mh-empty) mh))

(define (mh-find-min mh)
  (if (mh-empty? mh)
      (error 'mh-find-min "empty maxiphobic heap")
      (mh-item mh)))

(define (mh-delete-min lt? mh)
  (if (mh-empty? mh)
      (error 'mh-delete-min "empty maxiphobic heap")
      (mh-merge lt? (mh-lkid mh) (mh-rkid mh))))

(define (mh-sort lt? xs)
  (let loop1 ((xs xs) (mh mh-empty))
    (if (pair? xs)
        (loop1 (cdr xs) (mh-insert lt? (car xs) mh))
        (let loop2 ((mh mh) (zs '()))
          (if (mh-empty? mh)
              (reverse zs)
              (loop2 (mh-delete-min lt? mh)
                     (cons (mh-find-min mh) zs)))))))

(display (mh-sort > '(3 1 7 2 5 6 4)))


Output: 
1

(7 6 5 4 3 2 1)


Create a new paste based on this one


Comments: