diff options
author | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-10-05 21:49:54 +0200 |
---|---|---|
committer | Franciszek Malinka <franciszek.malinka@gmail.com> | 2021-10-05 21:49:54 +0200 |
commit | c5fcf7179a83ef65c86c6a4a390029149e518649 (patch) | |
tree | d29ffc5b86a0d257453cedcf87d91a13d8bf3b0d /Semestr 2/racket/leftist.rkt | |
parent | f8a88b6a4aba1f66d04711a9330eaba49a50c463 (diff) |
Duzy commit ze smieciami
Diffstat (limited to 'Semestr 2/racket/leftist.rkt')
-rw-r--r-- | Semestr 2/racket/leftist.rkt | 105 |
1 files changed, 0 insertions, 105 deletions
diff --git a/Semestr 2/racket/leftist.rkt b/Semestr 2/racket/leftist.rkt deleted file mode 100644 index 78319e4..0000000 --- a/Semestr 2/racket/leftist.rkt +++ /dev/null @@ -1,105 +0,0 @@ -#lang racket - -(provide make-elem elem-priority elem-val empty-heap heap-insert heap-merge heap-min heap-pop heap-empty?) - -(define (inc n) - (+ n 1)) - -;;; tagged lists -(define (tagged-list? len-xs tag xs) - (and (list? xs) - (= len-xs (length xs)) - (eq? (first xs) tag))) - -;;; ordered elements -(define (make-elem pri val) - (cons pri val)) - -(define (elem-priority x) - (car x)) - -(define (elem-val x) - (cdr x)) - -;;; leftist heaps (after Okasaki) - -;; data representation -(define leaf 'leaf) - -(define (leaf? h) (eq? 'leaf h)) - -(define (hnode? h) - (and (tagged-list? 5 'hnode h) - (natural? (caddr h)))) - -(define (make-hnode elem heap-a heap-b) - (if (< (rank heap-a) (rank heap-b)) - (list 'hnode elem (+ (rank heap-a) 1) heap-b heap-a) - (list 'hnode elem (+ (rank heap-b) 1) heap-a heap-b))) - -(define (hnode-elem h) - (second h)) - -(define (hnode-left h) - (fourth h)) - -(define (hnode-right h) - (fifth h)) - -(define (hnode-rank h) - (third h)) - -(define (hord? p h) - (or (leaf? h) - (<= p (elem-priority (hnode-elem h))))) - -(define (heap? h) - (or (leaf? h) - (and (hnode? h) - (heap? (hnode-left h)) - (heap? (hnode-right h)) - (<= (rank (hnode-right h)) - (rank (hnode-left h))) - (= (rank h) (inc (rank (hnode-right h)))) - (hord? (elem-priority (hnode-elem h)) - (hnode-left h)) - (hord? (elem-priority (hnode-elem h)) - (hnode-right h))))) - -(define (rank h) - (if (leaf? h) - 0 - (hnode-rank h))) - -;; operations - -(define empty-heap leaf) - -(define (heap-empty? h) - (leaf? h)) - -(define (heap-insert elt heap) - (heap-merge heap (make-hnode elt leaf leaf))) - -(define (heap-min heap) - (hnode-elem heap)) - -(define (heap-pop heap) - (heap-merge (hnode-left heap) (hnode-right heap))) - -(define (heap-merge h1 h2) - (cond - [(leaf? h1) h2] - [(leaf? h2) h1] - [else (let ((h1-min (heap-min h1)) - (h2-min (heap-min h2))) - (if (< (elem-priority h1-min) (elem-priority h2-min)) - (make-hnode h1-min (heap-merge (hnode-left h1) (hnode-right h1)) h2) - (make-hnode h2-min h1 (heap-merge (hnode-left h2) (hnode-right h2)))))])) - -;;; check that a list is sorted (useful for longish lists) -(define (sorted? xs) - (cond [(null? xs) true] - [(null? (cdr xs)) true] - [(<= (car xs) (cadr xs)) (sorted? (cdr xs))] - [else false])) |