1

以官方heapq为例：

>>> heap = []
>>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')]
>>> for item in data:
...     heappush(heap, item)
...
>>> while heap:
...     print(heappop(heap)[1])
J
O
H
N

我想进一步实现一个有效的selective_push，这样

  1. selected_push((1, 'M')) 等价于 heappush，因为 'M' 不在堆中
  2. selected_push((3.5, 'N')) 等价于 heap[2]= (3.5, 'N'); heapify(heap) 自 3.5<4
  3. 从 4.5>4 开始，selective_push((4.5, 'N')) 什么都不做

以下实现解释了目标，但速度很慢：

def selective_push(heap,s):
   NotFound=True
   for i in range(len(heap)): #linear search
        if heap[i][1]==s[1]:
            if s[0]<heap[i][0]:
                 heap[i]=s      #replacement
                 heapify(heap)
            NotFound=False
            break
    if NotFound:
       heappush(heap,s)

我认为由于线性搜索，它很慢，它破坏了 .log(n) 的复杂性heapq.push。替换率低，但总是执行线性搜索。

4

1 回答 1

1

heapq文档有一个如何更改现有项目优先级的示例。（该示例还使用 acount来确保具有相同优先级的项目以与添加它们的顺序相同的顺序返回：由于您没有提到这是一项要求，因此我通过删除该部分来简化代码。）我'还添加了您提到的与替换现有项目相关的逻辑。

从本质上讲，它归结为维护一个字典 ( entry_finder) 以快速查找项目，并将项目标记为已删除而不立即将它们从堆中删除，并在从堆中弹出时跳过标记的项目。

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        old_priority, _ = entry_finder[task]
        if priority < old_priority:
            # new priority is lower, so replace
            remove_task(task)
        else:
            # new priority is same or higher, so ignore
            return
    entry = [priority, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

一些注意事项：

  • heappush是高效的，因为它可以假设被推送到的列表已经作为堆排序；heapify每次调用时都必须检查所有元素

  • 没有真正删除项目，只是将它们标记为已删除，这很快，但确实意味着如果您要重置许多优先级，那么实际上会浪费一些存储空间；这是否合适取决于您的用例

  • 您需要为heapq要使用的任何其他函数创建类似的包装器，因为您始终需要确保entry_finder查找字典与 heapq 中的数据保持同步

于 2020-01-19T22:53:52.303 回答