擅长:python、mysql、java
<p><a href="https://docs.python.org/3/library/heapq.html" rel="noreferrer">The documentation</a>说</p>
<blockquote>
<p>Our pop method returns the smallest item, not the largest (called a
“min heap” in textbooks; a “max heap” is more common in texts because
of its suitability for in-place sorting).</p>
</blockquote>
<p>所以你不能直接得到最大堆。但是,一种间接获取它的方法是将项的<em>负</em>推到堆上,然后在弹出项后再次获取负。因此,不是<code>heappush(h, (200, 1))</code>,而是执行<code>heappush(h, (-200, -1))</code>。要弹出并打印最大项,请执行</p>
<pre><code>negmaxitem = heappop(h)
maxitem = (-negmaxitem[0], -negmaxitem[1])
print(maxitem)
</code></pre>
<p>有其他方法可以获得相同的效果,这取决于您到底在堆中存储了什么。</p>
<p>请注意,在最小堆中尝试<code>h[-1]</code>无法找到最大项——堆定义不能保证最大项最终会出现在列表的末尾。<code>nlargest</code>应该可以工作,但时间复杂度为<code>O(log(n))</code>,只需检查最小堆中最大的项,这就破坏了堆的目的。我的方法在负堆中有时间复杂度<code>O(1)</code>来检查最大的项。</p>