huffman encoding

huffman.rkt

#lang racket

;; Building a huffman encoding tree.
(require data/heap)

;; A node is either an interior, or a leaf.
;; In either case, they record an item with an associated frequency.
(struct interior (freq left right) #:transparent)
(struct leaf (val freq) #:transparent)


;; node-freq: node -> number
(define (node-freq a-node)
  (cond [(interior? a-node) (interior-freq a-node)]
        [(leaf? a-node) (leaf-freq a-node)]))


;; node<=?: node node -> boolean
(define (node<=? x y)
  (<= (node-freq x) (node-freq y)))

;; make-huffman-tree: (listof leaf) -> node
(define (make-huffman-tree leaves)
  (define a-heap (make-heap node<=?))
  (heap-add-all! a-heap leaves)
  (for ([i (in-range (sub1 (length leaves)))])
    (define min-1 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (define min-2 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (heap-add! a-heap (interior (+ (node-freq min-1) (node-freq min-2))
                                min-1 min-2)))
  (heap-min a-heap))