340

Python には最小ヒープ用の heapq モジュールが含まれていますが、最大ヒープが必要です。Python での最大ヒープの実装には何を使用すればよいですか?

4

17 に答える 17

364

最も簡単な方法は、キーの値を反転して heapq を使用することです。たとえば、1000.0 を -1000.0 に、5.0 を -5.0 に変更します。

于 2010-03-23T16:05:39.777 に答える
316

使用できます

import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]    
heapq.heapify(listForTree)             # for a min heap
heapq._heapify_max(listForTree)        # for a maxheap!!

要素をポップしたい場合は、次を使用します。

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
于 2014-05-13T16:10:52.173 に答える
122

解決策は、値をヒープに格納するときに値を無効にするか、次のようにオブジェクト比較を反転することです。

import heapq

class MaxHeapObj(object):
  def __init__(self, val): self.val = val
  def __lt__(self, other): return self.val > other.val
  def __eq__(self, other): return self.val == other.val
  def __str__(self): return str(self.val)

最大ヒープの例:

maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val  # fetch max value
x = heapq.heappop(maxh).val  # pop max value

ただし、値をラップおよびアンラップすることを忘れないでください。これには、最小ヒープまたは最大ヒープのどちらを扱っているかを知る必要があります。

MinHeap、MaxHeap クラス

MinHeapおよびオブジェクトのクラスを追加するとMaxHeap、コードを簡素化できます。

class MinHeap(object):
  def __init__(self): self.h = []
  def heappush(self, x): heapq.heappush(self.h, x)
  def heappop(self): return heapq.heappop(self.h)
  def __getitem__(self, i): return self.h[i]
  def __len__(self): return len(self.h)

class MaxHeap(MinHeap):
  def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
  def heappop(self): return heapq.heappop(self.h).val
  def __getitem__(self, i): return self.h[i].val

使用例:

minh = MinHeap()
maxh = MaxHeap()
# add some values
minh.heappush(12)
maxh.heappush(12)
minh.heappush(4)
maxh.heappush(4)
# fetch "top" values
print(minh[0], maxh[0])  # "4 12"
# fetch and remove "top" values
print(minh.heappop(), maxh.heappop())  # "4 12"
于 2016-11-06T23:32:47.010 に答える
13

heapq の最大ヒープ バージョンを実装し、PyPI に提出しました。(heapq モジュール CPython コードのごくわずかな変更。)

https://pypi.python.org/pypi/heapq_max/

https://github.com/he-zhe/heapq_max

インストール

pip install heapq_max

使用法

tl;dr: すべての関数に '_max' を追加する以外は、heapq モジュールと同じです。

heap_max = []                           # creates an empty heap
heappush_max(heap_max, item)            # pushes a new item on the heap
item = heappop_max(heap_max)            # pops the largest item from the heap
item = heap_max[0]                      # largest item on the heap without popping it
heapify_max(x)                          # transforms list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item)  # pops and returns largest item, and
                                    # adds new item; the heap size is unchanged
于 2016-08-03T00:44:40.510 に答える
12

これは、MaxHeapに基づく単純な実装ですheapq。数値でのみ機能しますが。

import heapq
from typing import List


class MaxHeap:
    def __init__(self):
        self.data = []

    def top(self):
        return -self.data[0]

    def push(self, val):
        heapq.heappush(self.data, -val)

    def pop(self):
        return -heapq.heappop(self.data)

使用法：

max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top())  # 5
于 2020-03-27T03:00:31.713 に答える
5

比較可能であるが int に似ていないキーを挿入する場合、それらの比較演算子を上書きする可能性があります (つまり、<= になる > および > になる <=)。それ以外の場合は、heapq モジュールで heapq._siftup をオーバーライドできます (最終的にはすべて単なる Python コードです)。

于 2010-03-23T16:11:19.637 に答える
1

値を反転して最大ヒープを作成するヒープ ラッパーと、ライブラリをより OOP 風にする最小ヒープのラッパー クラスを作成しました。これが要点です。3 つのクラスがあります。Heap (抽象クラス)、HeapMin、および HeapMax。

方法:

isempty() -> bool; obvious
getroot() -> int; returns min/max
push() -> None; equivalent to heapq.heappush
pop() -> int; equivalent to heapq.heappop
view_min()/view_max() -> int; alias for getroot()
pushpop() -> int; equivalent to heapq.pushpop
于 2016-06-11T14:56:09.467 に答える
0

Isaac Turner の優れた回答に続いて、最大ヒープを使用してオリジンに最も近い K 個のポイントに基づく例を挙げたいと思います。

from math import sqrt
import heapq


class MaxHeapObj(object):
    def __init__(self, val):
        self.val = val.distance
        self.coordinates = val.coordinates

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

    def __eq__(self, other):
        return self.val == other.val

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


class MinHeap(object):
    def __init__(self):
        self.h = []

    def heappush(self, x):
        heapq.heappush(self.h, x)

    def heappop(self):
        return heapq.heappop(self.h)

    def __getitem__(self, i):
        return self.h[i]

    def __len__(self):
        return len(self.h)


class MaxHeap(MinHeap):
    def heappush(self, x):
        heapq.heappush(self.h, MaxHeapObj(x))

    def heappop(self):
        return heapq.heappop(self.h).val

    def peek(self):
        return heapq.nsmallest(1, self.h)[0].val

    def __getitem__(self, i):
        return self.h[i].val


class Point():
    def __init__(self, x, y):
        self.distance = round(sqrt(x**2 + y**2), 3)
        self.coordinates = (x, y)


def find_k_closest(points, k):
    res = [Point(x, y) for (x, y) in points]
    maxh = MaxHeap()

    for i in range(k):
        maxh.heappush(res[i])

    for p in res[k:]:
        if p.distance < maxh.peek():
            maxh.heappop()
            maxh.heappush(p)

    res = [str(x.coordinates) for x in maxh.h]
    print(f"{k} closest points from origin : {', '.join(res)}")


points = [(10, 8), (-2, 4), (0, -2), (-1, 0), (3, 5), (-2, 3), (3, 2), (0, 1)]
find_k_closest(points, 3)
于 2019-12-12T18:50:08.207 に答える