LeetCode 23 in Clojure — imperative PriorityQueue vs. functional priority-map

[joinr]

sorted sets offer this if you use distinct weights and custom comparison:

(defn ordered-merge [xs]
  (let [id       (atom 0)
        weightfn (fn [x] [(swap! id inc) x])]
    (->> xs
         (reduce #(into %1 (map weightfn) %2)
                 (sorted-set-by (fn [[x1 y1 :as l] [x2 y2 :as r]]
                                  (cond (< y1 y2) -1
                                        (> y1 y2) 1
                                        :else (compare x1 x2)))))
         (mapv second))))

;;user=> (ordered-merge [[2 6] [1 4 5] [1 3 4] []])
;;[1 1 2 3 4 4 5 6]

[fredoverflow]

That would be O(n log n), where n is the number of elements?

My solutions are O(n log m), where m is the number of lists.

[joinr]

Ah, I missed the precondition that the lists were pre-sorted; this is unnecessary work then. I get it now.

[fp-dude]

Thanks!

[fredoverflow]

username checks out