Реализация Min / Max Heap в Python - PullRequest
Новая
       75

Реализация Min / Max Heap в Python

0 голосов
/ 07 мая 2018

Это моя реализация MinHeap и MaxHeap в Python. При этом используется компаратор для изменения последовательности хранения в MaxHeap 

import heapq


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

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

    def __getitem__(self, item):
        return self.heap[item]

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


class MaxHeap(MinHeap):
    def push(self, item):
        heapq.heappush(self.heap, Comparator(item))

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

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


class Comparator:
    def __init__(self, val):
        self.val = val

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

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




if __name__ == '__main__':
    max_heap = MaxHeap()
    max_heap.push(12)
    max_heap.push(3)
    max_heap.push(17)
    print(max_heap.pop())

MinHeap, кажется, работает нормально, однако MaxHeap выдает следующую ошибку. 

<__main__.Comparator object at 0x10a5c1080>

Я не совсем понимаю, что я здесь делаю не так. Может ли кто-нибудь помочь мне с этим.

1 Ответ

0 голосов
/ 07 мая 2018

Я добавил __repr__ и __gt__ методы в ваш класс Comparator, поэтому код теперь выполняется, и экземпляры Comparator отображают свои val при печати. ​​

Важно, чтобы эти методы сравнения правильно выполняли сравнения между двумя Comparator экземплярами.

Вы заметите, что я исключил большинство методов из MaxHeap. Они не нужны, потому что методы, унаследованные от MinHeap, работают нормально. Вы можете восстановить это значение до MaxHeap

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

в зависимости от того, как вы собираетесь использовать MaxHeap. 

import heapq

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

    def push(self, item):
        heapq.heappush(self.heap, item)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        return self.heap[0]

    def __getitem__(self, item):
        return self.heap[item]

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

class MaxHeap(MinHeap):
    def push(self, item):
        heapq.heappush(self.heap, Comparator(item))

class Comparator:
    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 __repr__(self):
        return repr(self.val)

if __name__ == '__main__':
    max_heap = MaxHeap()
    max_heap.push(12)
    max_heap.push(3)
    max_heap.push(17)

    while True:
        try:
            print(max_heap.pop())
        except IndexError:
            # The heap's empty, bail out
            break

выход 

17
12
3

Вероятно, это хорошая идея, чтобы дать Comparator полный набор богатых методов сравнения. Они не нужны для того, чтобы приведенный выше код работал, но они сделают экземпляры Comparator более гибкими. Так что, если вы хотите их, вот они: 

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

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

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

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

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

def __ne__(self, other):
    return self.val != other.val
...