2
\$\begingroup\$

I'm going to write a Huffman Coding implementation, and decided to write from scratch a priority queue to help out. I've never written a priority queue before, in any language, so this was interesting.

After mulling over the design for a bit, I finally settled on a linked list design. The queue is essentially just a linked list with a size field. When a value is added, it recursively walks the list until it finds the right spot, and wedges it in as a new node. This may not be optimal, but peeks/pops are O(1), so it's sufficient. The only issue is pushes can be inefficient, as they may require walking the entire list if a low priority item is added.

This isn't my final attempt. I think I'm going to have it implement the standard protocols for consistency with the standard structures. For now though, the -queue suffixes/prefixes will do.

I'd like mainly my design critiqued here. I threw this down in only half an hour, tested it, and am fairly happy with it, but it wouldn't surprise me if I'm doing something overly roundabout. I'll welcome any critique though.

Example:

(let [q (new-priority-queue)]
  (-> q
      (push-queue 1 :hello)
      (push-queue 0 :new-root)
      (push-queue 5 :worst)
      (push-queue 3 :middle)
      (clojure.pprint/pprint)))

{:root
 {:priority 0,
  :bucket [:new-root],
  :child
  {:priority 1,
   :bucket [:hello],
   :child
   {:priority 3,
    :bucket [:middle],
    :child {:priority 5, :bucket [:worst], :child nil}}}},
 :size 4}

(ns huffman.priority-queue.attempt1)

(defrecord Priority-Queue [root size])
(defrecord Node [priority bucket child])

(defn new-node [priority value]
  (->Node priority [value] nil))

(defn- add-value-to-node [node value]
  (update node :bucket conj value))

(defn- set-child-of-node [node child]
  (assoc node :child child))

(defn new-priority-queue []
  (->Priority-Queue nil 0))

(defn queue-empty? [queue]
  ; FIXME: Just check if the root is nil?
  (zero? (:size queue)))

(defn- push-new-node [queue priority value]
  (let [node (new-node priority value)]
    (update queue :root
      (fn rec [{n-pri :priority, n-child :child :as root}]
        (cond
          (nil? root) node
          (< priority n-pri) (set-child-of-node node root)
          (= priority n-pri) (add-value-to-node root value)
          :else (set-child-of-node root (rec n-child)))))))

(defn push-queue
  "Pushes the value with a given priority into the queue."
  [queue priority value]
  (when-not value
    (throw (RuntimeException. (str "Pushed values must be truthy!: " (pr-str value)))))

  (-> queue
      (push-new-node priority value)
      (update :size inc)))

(defn peek-priority?
  "Returns either the highest priority item, or nil if the queue is empty.
  If multiple items have the same priority, the first pushed item is returned."
  [queue]
  (when-not (queue-empty? queue)
    (-> queue :root :bucket (first))))

(defn- remove-priority [queue]
  (update queue :root
    (fn [root]
      (if (= (count (:bucket root)) 1)
        (:child root)
        (update root :bucket subvec 1)))))

(defn pop-priority?
  "Returns either a pair of [highest-priority rest-queue], or nil if the queue is empty."
  [queue]
  (when-not (queue-empty? queue)
    (let [popped (peek-priority? queue)
          rest-queue (remove-priority queue)]
      [popped (update rest-queue :size dec)])))

Just a note: right now, lower valued priorities are considered higher priority (since I had Huffman Coding in mind while writing this). I'm going to add a comparator field to the queue record in the future though, and use the custom comparator in push-new-node to allow for a user-defined ordering.

\$\endgroup\$
  • \$\begingroup\$ Ppsh, I just realized, immediately after posting that pop-priority? could just make use of the fact that peek-priority? returns nil if empty, and just use when-let. -_-. \$\endgroup\$ – Carcigenicate May 27 '18 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.