heapify 函数不给出排序列表

Question

heapq.heapify() 是如何运作的？我正在尝试使用堆找到中位数。 heapify returns 我有条不紊当我使用 heapq.heappush() 添加元素时，它被插入到列表中。当我再次调用 heapify 时，返回的列表未排序。

import heapq

l=[5,15,1,3]

heapq.heapify(l)

print(l)

这给了我 [1, 3, 5, 15]

但是当我添加 heapq.heappush(l,2) 它 returns

[1, 2, 5, 15, 3]

当我再做一次时heapq.heapify(l)

不过，它给了我同样的结果。

[1, 2, 5, 15, 3]

如何使用堆来实现求中值？列表应该排序吗？

Answer 1

如果每次添加元素后都需要排序列表，请尝试将这些元素添加到列表中（附加它们）。然后像你一样堆化列表。它每次都会给你排序列表。 :-)

Answer 2

如果您查看 theory section of heapq，您会发现它不会对您的列表进行排序。但它把它们放在一个带有 奇怪不变量 :

的顺序中

lst[k] <= lst[2*k+1] and lst[k] <= lst[2*k+2]

这对你的清单很满意；如果您以 'binary tree' 形式查看它：

      1
  2       5
15  3

2小于15和3。满足条件。 5 与 non-existing 个元素（被认为是无限的 - 因此条件成立）进行比较。

为了对您的列表进行排序，您最好使用 sorted:

lst = sorted(lst)
# [1, 3, 5, 15]

然后 高效地 在一个已经排序的列表中插入 bisect 模块：

from bisect import insort_left
insort_left(lst, 2)
# [1, 2, 3, 5, 15]

现在的中位数是 lst[len(lst)//2]。

print(f"median = {lst[len(lst)//2]}")
# median = 3

或者，根据您的约定（这里是 statistics.median 中使用的约定）：

def median(lst):
    ln = len(lst)
    if ln % 2 != 0:
        return lst[ln // 2]
    else:
        return (lst[ln // 2 - 1] + lst[ln // 2]) / 2

heapify function does not give sorted list