#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)
  (define x (rank heap-a))
  (define y (rank heap-b))
  (if (<= x y)
      (list 'hnode elem (inc x) y x)
      (list 'hnode elem (inc y) x y)))


(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]
   ;; XXX: fill in the implementation
   [else
   (define kopiecx (heap-min h1))
   (define kopiecy (heap-min h2))
   (define x (hnode-elem kopiecx))
   (define y (hnode-elem kopiecy))
   (if (<= (elem-priority x) (elem-priority y))
       (make-hnode x (heap-merge (hnode-right kopiecx) kopiecy) (hnode-left kopiecx))
       (make-hnode y (heap-merge (hnode-right kopiecy) kopiecx) (hnode-left kopiecy)))
    ]))

;;; 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]))


(define (heapsort lista)
  (define (wstaw xs)
    (if (= (length xs) 0)
        leaf
        (heap-insert (make-elem (car xs) (car xs)) (wstaw (cdr xs)))))
  (define (wynik h)
    (if (heap-empty? h)
        null
        (append (list (heap-min h)) (list (wynik (heap-pop h))))))
  (wynik (wstaw lista))
  )

(heapsort (list 4 7 5 2))