Удалить произвольный элемент из кучи в Python

Question

Есть ли реализация двоичной кучи, где я могу вытолкнуть другие элементы, кроме корня, в log n раз?

Я использую heapq - но heap.index( wKeys ) в

heap.pop( heap.index( wKeys ) )

очень медленно Мне нужна двоичная куча для моей проблемы - где я когда-нибудь использую

heapq.heappop(heap)

но также нужно вытолкнуть другие элементы, чем в верхней части кучи. Таким образом, двоичная куча, такая как реализация heapq, должна делать это, но я не нашел метод двоичного поиска. Я также посмотрел на Treap ( http://stromberg.dnsalias.org/~strombrg/treap/) и не могу найти здесь такой метод.

Answer 1

Я изменил реализацию heapq, добавив параметр heappop(), а также heappush() - который heapIndex, Это занимает словарь {item: index} и обновляет heapIndex как он появляется или толкает heap,

Я также добавил новый метод heappop_arbitrary() который удаляет произвольный элемент и обновляет heapIndex

Код доступен здесь: https://github.com/emoen/heapq_with_index

Я переименовал методы heappop(),heappush() в heappop2(), heappush2() чтобы избежать путаницы с оригинальными методами.

Я не реализовал это ни для одной из других функций, доступных в heapq.

Answer 2

class RemoveHeap:
    def __init__(self):
        self.h = []
        self.track = collections.defaultdict(collections.deque)
        self.counter = itertools.count()

    def insert_item(self, val):
        count = next(self.counter)
        item = [val, count, 'active']
        self.track[val].append(item)
        heapq.heappush(self.h, item)

    def delete_item(self, val):
        if val in self.track:
            items = self.track[val]
            for item in items:
                if item[2] == 'active':
                    item[2] = 'deleted'
                    break

    def pop_item(self):
        while len(self.h) > 0:
            item = heapq.heappop(self.h)
            item_track = self.track[item[0]]
            item_track.popleft()
            if len(item_track) == 0:
                del self.track[item[0]]
            else:
                self.track[item[0]] = item_track
            if item[2] == 'active':
                return item[0]

    def peek_item(self):
        item = self.h[0]
        if item[2] == 'deleted':
            x = self.pop_item()
            self.insert_item(x)
            return x
        return item[0]