median-finder-test.clj

median-finder-test.clj

(ns median-finder-test
  (:require [clojure.test :refer :all])
  (:import [java.util PriorityQueue Collections]))

;; Leetcode reference: https://leetcode.com/problems/find-median-from-data-stream/description/

;; Find Median from Data Stream
;; The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
;For example, for arr = [2,3,4], the median is 3.
;For example, for arr = [1,2,3,10], the median is (2 + 3) / 2 = 2.5.

;; ADD:
;; if left heap is empty or peek of left heap is > num - add to left heap
;; else add to the right heap
;;
;; handle imbalances: if left size - right size > 1, move peek element from left to right
;; if opposite keep as is

;; MEDIAN:
;; if both heaps are empty - nil
;; if one is > the other - peek from the bigger heap
;; else get average from both heaps
;;
;;

;; HEAPS
;; Complete Binary Tree: A min-heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly the last level, which is filled from left to right.
;
;Min-Heap Property: For every node i, the value of i is less than or equal to the values of its children. This guarantees that the minimum element is at the root of the heap.
;
;Efficient Operations: Common operations such as inserting an element or removing the minimum element are efficient. These operations have a time complexity of O(log n), where n is the number of elements in the heap.

(defn median-finder []
  (let [left (PriorityQueue. (Collections/reverseOrder))
        right (PriorityQueue.)]
    {:add-num (fn [num]
                (if (or (.isEmpty left)
                        (< num (.peek left)))
                  (.offer left num)
                  (.offer right num))
                (let [ls (.size left)
                      rs (.size right)]
                  (cond
                    (> (- ls rs) 1) (.offer right (.poll left))
                    (> (- rs ls) 1) (.offer left (.poll right)))))
     :find-median (fn []
                    (let [peek (fn [heap]
                                 (some-> heap (.peek) (double)))
                          ls (.size left)
                          rs (.size right)
                          l (peek left)
                          r (peek right)]
                      (cond
                        (= ls rs 0) nil
                        (> ls rs) l
                        (> rs ls) r
                        :else (/ (+ l r) 2.0))))}))

(deftest median-finder-test
  (let [{:keys [add-num find-median]} (median-finder)]
    (is (nil? (find-median)))
    (add-num 1)
    (add-num 2)
    (is (= 1.5 (find-median)))
    (add-num 3)
    (is (= 2.0 (find-median)))))