Hylangで最大ヒープ

概要

　Pythonの組み込みライブラリにはheapqなる、ヒープ木を実現するためのモジュールがあるのだが、最小ヒープしか対応していないので、小細工して最大ヒープをできる様にしてみた。
　※ ただし言語はHylang

最大ヒープって何？

　ヒープ木でルートの値が最大値のもの。
　詳しくは、http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B&lang=jpを参照

実装

　比較演算子のオーバーライドでどうにかしてみた。

;; ----------------------------------------
;; Max Heap : ルートが最大値
;; ----------------------------------------
(import [heapq [heappush heappop]])

(defclass ReverseOrder []
  []
  (defn --init-- [self x]
    (setv (. self _x) x))
  (defn --lt-- [self other]
    (> (. self _x) (. other _x)))
  (defn --le-- [self other]
    (>= (. self _x) (. other _x)))
  (defn --gt-- [self other]
    (< (. self _x) (. other _x)))
  (defn --ge-- [self other]
    (<= (. self _x) (. other _x)))
  (defn --str-- [self]
    (-> (. self _x) str)))

(defn heap-push [que x]
  (heappush que (ReverseOrder x)))

(defn heap-pop [que]
  (. (heappop que) _x))


;;; テスト
(def xs [])
(heap-push xs 2)
(heap-push xs 3)
(heap-push xs 1)
(print (heap-pop xs)) ;; 3

おまけ

　流石にHylangの需要がなさすぎるので、Python Versionも公開しておく。

from heapq import heappush, heappop


class ReverseOrder:

    def __init__(self, x):
        self._x = x
        return None

    def __lt__(self, other):
        return (self._x > other._x)

    def __le__(self, other):
        return (self._x >= other._x)

    def __gt__(self, other):
        return (self._x < other._x)

    def __ge__(self, other):
        return (self._x <= other._x)

    def __str__(self):
        return str(self._x)

def heap_push(que, x):
    return heappush(que, ReverseOrder(x))

def heap_pop(que):
    return heappop(que)._x

## テスト
xs = []
heap_push(xs, 2)
heap_push(xs, 3)
heap_push(xs, 1)
print (heap_pop(xs)) # 3