使用堆数据结构查找最小值并在列表上进行一些计算

Question

我正在研究堆并在 hackarank 中尝试了一个问题。

问题是找出在一个列表中达到某个值 K 所花费的次数。如果任何值小于 K：则添加前两个最小值并放置新值而不是这两个值。

我已经完成了解决方案的编码。但是，请说明我可以做哪些改进以使代码运行更快。

我的代码：

import heapq as heap

data = map (int, raw_input ().strip ().split ())
N, K = data [0], data [1]

cookies = map (int, raw_input ().strip ().split ()) 
heap.heapify (cookies)
numOps = 0
possibility = False

while cookies [0] < K:
    if N == 1:
        possibility = True
        break
    leastSweetCookies = heap.nsmallest (2, cookies)
    heap.heapreplace (cookies, leastSweetCookies [0] + 2 * leastSweetCookies [1])
    heap.heappop (cookies)
    numOps += 1
    N -= 1
if possibility == False: print numOps
else: print -1

Answer 1

这三行：

leastSweetCookies = heap.nsmallest (2, cookies)
heap.heapreplace (cookies, leastSweetCookies [0] + 2 * leastSweetCookies [1])
heap.heappop (cookies)

相当于：

sw1 = heap.heappop(cookies);
sw2 = heap.heappop(cookies);
heap.heappush(cookies, sw1 + 2*sw2);

在您的代码中，对 nsmallest 的调用可能会遍历整个堆以找到 2 个最小的项目。然后是一个O(log n)的替换top元素，O(log n)弹出最小的。

在替换代码中，两次弹出的时间均为 O(log n)，而推送的时间为 O(log n)。所以：

你的代码：O(n) + O(log n) + O(log n)

我的代码：O(log n) + O(log n) + O(log n)

使用堆数据结构查找最小值并在列表上进行一些计算

Finding minimum and do some calculations on list using heap data structure

python

sorting

heap