python堆排序heapq

heapq模块实现了一个适用于Python列表的最小堆排序算法。

堆是一种树形数据结构,其中子节点与父节点之间是一种有序关系。最大堆中父节点大于或等于两个子节点,最小堆父节点小于或等于两个子节点。Python的heapq模块实现了一个最小堆。

创建堆

创建堆有两种方式,heappush()和heapify()。

import heapq

data = [1,5,3,2,8,5]
heap = []

for n in data:
    heapq.heappush(heap, n)

如果数据已经存在于内存中,使用heapify()原地重新组织列表中的元素会更加高效。

import heapq

data = [1,5,3,2,8,5]
heapq.heapify(data)

上述两种方法得到的堆是一样的。

还有一种merge()方法,可以从多个可迭代对象中创建一个堆,相当于heapq.heapify(itertools.chain(*iterables))

访问堆内容

堆创建好之后,可以使用heappop()删除有最小值的元素。

import heapq

data = [1,5,3,2,8,5]
heapq.heapify(data)

print heapq.heappop(data) # print 1

如果希望在一个操作中删除现有最小元素并替换成新值,可以使用heapreplace()。

import heapq

data = [1,5,3,2,8,5]
heapq.heapify(data)
heapq.heapreplace(data,10)

堆的数据极值

heapq还包括两个检查可迭代对象的函数,查找其中包含的最大值与最小值的范围。

import heapq

data = [1,5,3,2,8,5]
print heapq.nlargest(3, data)
print heapq.nsmallest(3, data)

输出结果如下:

[8, 5, 5]
[1, 2, 3]

只有在n值比较小的情况下nlargest()和nsmallest()才比较高效。

这个两个函数还接受一个关键字参数key, 用于更加复杂的数据结构中。

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

上面代码对每个元素进行比较时, 会以price的值进行比较。

实战

实现堆排序:

>>> from heapq import *
>>> def heapsort(iterable):
...     'Equivalent to sorted(iterable)'
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

由于堆中的元素可以为元组,所以可以对带权值的元素进行排序。

>>> from heapq import *
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

参考 《python参考手册》 《python标准库》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

走近 Python (类比 JS)

Python 是一门运用很广泛的语言,自动化脚本、爬虫,甚至在深度学习领域也都有 Python 的身影。作为一名前端开发者,也了解 ES6 中的很多特性借鉴自 ...

41610
来自专栏轮子工厂

6. 简单又复杂的“运算符”,建议你看一哈

昨天的《5. 很“迷”的字符与字符串》初稿本来很短的,但是我觉得内容太少了,就加了一些,结果好像就变得特别多〒▽〒。

893
来自专栏编程

Python入门基础连载(4)控制流

Python控制流语句有三种————if,for,while,有相关语言类似C,java的同学应该不会陌生的,下面我们就做下介绍: if语句 if语句用来检验一...

1986
来自专栏我是攻城师

理解插入排序,希尔排序,选择排序的算法原理

在前面的文章中,其实已经把效率比较高的排序算法给分析过了,比如比较通用的快排,归并排序和堆排,还有用于特定场景的计数排序等。本篇我们把剩下的几种效率一般的排序算...

1031
来自专栏IT可乐

Java数据结构和算法(六)——前缀、中缀、后缀表达式

  前面我们介绍了三种数据结构,第一种数组主要用作数据存储,但是后面的两种栈和队列我们说主要作为程序功能实现的辅助工具,其中在介绍栈时我们知道栈可以用来做单词逆...

2619
来自专栏武培轩的专栏

Leetcode#557. Reverse Words in a String III(反转字符串中的单词 III)

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

773
来自专栏程序员互动联盟

【编程基础】C++ Primer快速入门之七:运算符

一、表达式的定义 什么是表达式?表达式,是由数字、运算符、数字分组符号(括号)、自由变量和约束变量等以能求得数值的有意义排列方法所得的组合(1)。1 + 2是个...

3154
来自专栏C语言C++游戏编程

有人@我,你有一份C语言基础大全手册要领取,快来拿!

前两天,有网友问了我一个关于C语言的问题,本着认真装逼的态度,我把大学时学过的C语言课本翻了一遍,终于找到了答案。整理后,现分享给大家!

1432
来自专栏十月梦想

php字符串基本操作

字符串查找strstr(查找目标字符串,查找关键词),stristr(查找目标字符串,查找关键词)

691
来自专栏从流域到海域

《笨办法学Python》 第19课手记

《笨办法学Python》 第19课手记 本节课讲函数和变量(变量和函数的关系是变量作为做函数的参数,定义时是形参,使用时是实参),内容比较简单。 源代码如下: ...

25010

扫码关注云+社区

领取腾讯云代金券