编码任务在这里
堆解决方案：
import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
return heapq.nsmallest(K, points, key = lambda P: P[0]**2 + P[1]**2)
排序解决方案：
class Solution(object):
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
points.sort(key = lambda P: P[0]**2 + P[1]**2)
return points[:K]
根据此处的解释，Python的heapq.nsmallest为O（n log（t）），而Python List.sort（）为O（n log（n））。但是，我的提交结果显示排序比heapq快。这怎么发生的？从理论上讲是相反的，不是吗？
如何访问 heapq 中的顶部元素而不删除（弹出）它 python ？
我只需要检查堆顶部的元素而不弹出它。我怎样才能做到这一点。
def heapify(A):
for root in xrange(len(A)//2-1, -1, -1):
rootVal = A[root]
child = 2*root+1
while child < len(A):
if child+1 < len(A) and A[child] > A[child+1]:
child += 1
if rootVal <= A[child]:
break
A[child], A[(child-1)//2] = A[(child-1)//2], A[child]
child = child *2 + 1
这是python heapq.heapify（）的类似实现。据说在文档中此函数在O（n）中运行。但是，对于n / 2个元素，它似乎执行log（n）操作。为什么是O（n）？
我正在尝试在程序中使用 Python 模块，heapq但使用heapq.heappop(). 该函数似乎没有返回堆中的最小元素。看一下下面的代码：
Python 2.7.12 (default, Jul 1 2016, 15:12:24)
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import heapq
>>> list = [[1326, 'a'], [654, 'b']]
>>> print heapq.heappop(list)
[1326, 'a']
>>> print heapq.heappop(list)
[654, 'b']
不应该先heappop()返回[654, 'b']再返回[1326, 'a']吗？
我读到 heapq.merge 函数专门用于合并 2 个排序数组？时间复杂度是 O(n) 吗？如果不是，那是什么？为什么？还有它的空间复杂性是什么。
我正在解决将 2 个排序数组与 2 个指针合并的问题，并且可以实现 O(n) 时间复杂度和 O(n) 空间复杂度。
我试图重新实现 heapify 方法，以便使用_siftup和_siftdown更新或删除堆中的任何节点并保持 O(log(n)) 的时间复杂度。
我做了一些努力来优化我的代码，但事实证明它们比heapq.heapify （就花费的总时间而言）更糟糕。所以我决定研究源代码。并将复制的代码与模块的代码进行比较。
# heap invariant.
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
def _siftup(heap, pos):
endpos = len(heap)
startpos = pos …>>> from heapq import heappush
>>> heap = []
>>> heappush(heap,(0,{"k":0}))
>>> heappush(heap,(0,{"k":1}))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'
python2和 python3的官方 heapq 文档中提到了这一点，该文档建议使用 DIY 实现来缓解此问题。heapq
为什么会发生这种情况？heapq鉴于这是一个非常旧的库，这种冲突没有得到解决的根本原因是什么？是否有性能/其他问题？为什么我们不能只提供参数keep_old, keep_any作为该库的功能？
从维基百科
二叉堆的定义来看，sift-up也称为up-heap操作，sift-down称为down-heap。
所以在堆（完全二叉树）中，up表示从叶到根，down表示从根到叶。
但在Python中，情况似乎恰恰相反。siftup我对and的含义感到困惑siftdown，并且在第一次使用时被误用。
_siftdown以下是和_siftup中的 python 版本实现heapq：
# 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
# is the index of a leaf with a possibly out-of-order value. Restore the
# heap invariant.
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding …为什么这个优先级队列无法堆化？其中 (150, 200, 200) 是分配给字典的优先级值
import heapq
priority_q = [
(150, {'intel-labels': {'timestamp': 150}}),
(200, {'intel-labels': {'timestamp': 200}}),
(200, {'intel-labels': {'timestamp': 200, 'xx': 'xx'}})
]
heapq.heapify(priority_q)
print( heapq.nlargest(2, priority_q))
例外情况：
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'
然而，下面的工作原理..
priority_q = [
(150, {'intel-labels': {'timestamp': 150}}),
(200, {'intel-labels': {'timestamp': 200}}),
(201, {'intel-labels': {'timestamp': 200, 'xx': 'xx'}})
]
heapq.heapify(priority_q)
为什么是这样？
我正在使用python进行工作，而heapq出现了一些问题。当我将元素推入堆时，我收到此错误：
TypeError：“ Point”和“ Point”的实例之间不支持“ <”
重点是我的内部课程。我推入由（float，Point）组成的元组，根据文档，heapq应该使用float作为键，但事实并非如此。为了更精确，有时使用float而不是总是使用。问题是什么？