Heapify函数不提供排序列表 [英] heapify function does not give sorted list

问题描述

heapq.heapify()如何工作？ 我正在尝试使用堆来寻找中位数。 heapify返回排序方式 当我使用heapq.heappush()添加元素时，使用它被插入到列表中。 当我再次调用heapify时，返回的列表未排序。

import heapq

l=[5,15,1,3]

heapq.heapify(l)

print(l)

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

但是当我添加heapq.heappush(l,2)时 它返回

[1, 2, 5, 15, 3]

当我再次执行操作时heapq.heapify(l)

尽管如此，它还是给了我同样的东西。

[1, 2, 5, 15, 3]

如何使用堆实现求中值？是否应该对列表进行排序？

推荐答案

如果您查看theory section of heapq，您会发现它不会对您的列表进行排序。但它使用奇怪的不变量：

对它们进行排序

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

这对您的列表是令人满意的；如果您以二叉树的形式查看它：

      1
  2       5
15  3

2小于15和3。它满足条件。5与不存在的元素(被认为是无限的，因此条件成立)进行比较。

---

为了对列表进行排序，您最好使用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函数不提供排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！