Python堆排序之heapq

Python中的堆排序

heapq模块实现了Python中的堆排序,并提供了有关方法。让用Python实现排序算法有了简单快捷的方式。

heapq的官方文档和源码:Heap queue algorithm

下面通过举例的方式说明heapq的应用方法

实现堆排序

from heapq import *


def heap_sort(iterable):
    h = []
    for value in iterable:
        heappush(h, value)
    return [heappop(h) for _ in range(len(h))]


if __name__ == '__main__':
    print(heap_sort([1, 3, 5, 9, 2, 123, 4, 88]))

Output: [1, 2, 3, 4, 5, 9, 88, 123]

下面说说几个主要方法

heappush()

heapq.heappush(heap, item):将item压入到堆数组heap中。如果不进行此步操作,后面的heappop()失效

heappop()

>>> h = []                    #定义一个list
>>> from heapq import *     #引入heapq模块
>>> h
[]
>>> heappush(h, 5)               #向堆中依次增加数值
>>> heappush(h, 2)
>>> heappush(h, 3)
>>> heappush(h, 9)
>>> h                           #h的值
[2, 5, 3, 9]
>>> heappop(h)                  #从h中删除最小的,并返回该值
2
>>> h
[3, 5, 9]
>>> h.append(1)                 #注意,如果不是压入堆中,而是通过append追加一个数值
>>> h                           #堆的函数并不能操作这个增加的数值,或者说它堆对来讲是不存在的
[3, 5, 9, 1]
>>> heappop(h)                  #从h中能够找到的最小值是3,而不是1
3
>>> heappush(h, 2)               #这时,不仅将2压入到堆内,而且1也进入了堆。
>>> h
[1, 2, 9, 5]
>>> heappop(h)                  #操作对象已经包含了1
1

heapq.heappushpop(heap, item)

是上述heappush和heappop的合体,同时完成两者的功能.注意:相当于先操作了heappush(heap,item),然后操作heappop(heap)

>>> h
[1, 2, 9, 5]
>>> heappop(h)
1
>>> heappushpop(h, 4)            #增加4同时删除最小值2并返回该最小值,与下列操作等同:
2                               #heappush(h,4),heappop(h)
>>> h
[4, 5, 9]

heapq.heapify(x)

x必须是list,此函数将list变成堆,实时操作。从而能够在任何情况下使用堆的函数。

>>> a = [3, 6, 1]
>>> heapify(a)                  #将a变成堆之后,可以对其操作
>>> heappop(a)
1
>>> b = [4, 2, 5]                   #b不是堆,如果对其进行操作,显示结果如下
>>> heappop(b)                  #按照顺序,删除第一个数值并返回,不会从中挑选出最小的
4
>>> heapify(b)                  #变成堆之后,再操作
>>> heappop(b)
2

heapq.heapreplace(heap, item)

是heappop(heap)和heappush(heap,item)的联合操作。注意,与heappushpop(heap,item)的区别在于,顺序不同,这里是先进行删除,后压入堆

>>> a = []
>>> heapreplace(a, 3)            #如果list空,则报错
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
>>> heappush(a, 3)
>>> a
[3]
>>> heapreplace(a, 2)            #先执行删除(heappop(a)->3),再执行加入(heappush(a, 2))
3
>>> a
[2]
>>> heappush(a, 5)  
>>> heappush(a, 9)
>>> heappush(a, 4)
>>> a
[2, 4, 9, 5]
>>> heapreplace(a, 6)            #先从堆a中找出最小值并返回,然后加入6
2
>>> a
[4, 5, 9, 6]
>>> heapreplace(a, 1)            #1是后来加入的,在1加入之前,a中的最小值是4
4
>>> a
[1, 5, 9, 6]

heapq.merge(\*iterables)

举例:

>>> a = [2, 4, 6]         
>>> b = [1, 3, 5]
>>> c = merge(a, b)
>>> list(c)
[1, 2, 3, 4, 5, 6]

在[归并排序](https://github.com/qiwsir/algorithm/blob/master/merge_sort.md)中详细演示了本函数的使用方法。

heapq.nlargest(n, iterable[, key]),heapq.nsmallest(n, iterable[, key])

获取列表中最大、最小的几个值。

>>> a   
[2, 4, 6]
>>> nlargest(2,a)
[6, 4]

数组中的第K个最大元素

其实以上说了那么多,只是为了说这道题。

在未排序的数组中找到第 **k** 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

这里不说别的解法。当然面试中你肯定不能这么写,但这是一个很好的思路

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        import heapq 
        heapq.heapify(nums) 
        return heapq.nlargest(k, nums)[-1]

看到有人用 return sorted(nums)[-k],真的要被气死了。

同九年 汝独秀

参考 https://github.com/qiwsir/algorithm/blob/master/heapq.md

本文分享自微信公众号 - Python爬虫与算法进阶(zhangslob)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-05

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 说一道排序题

    关于Python的sorted排序算法,这篇文章讲的比较详细:python sort函数内部实现原理,说到Python使用的是著名的Timesort算法。

    小歪
  • 【萌新写爬虫】爬知乎关注信息

    这个例子是【爬虫工程师课程】中的一个实战,这里简单介绍下。 记得以前说过,爬虫有三步:获取源码、解析源码、储存数据。首先看看知乎的数据在哪里。 一、分析网页请求...

    小歪
  • Python爬淘宝——300W淘宝文胸说明了什么

    项目地址:https://github.com/nladuo/taobao_bra_crawler 作者:叁公子KCN ? 爬虫部署 部署环境 测试环境:腾讯...

    小歪
  • 探寻微博背后的大数据原理:微博推荐算法简述

    在介绍微博推荐算法之前,我们先聊一聊推荐系统和推荐算法。有这样一些问题:推荐系统适用哪些场景?用来解决什么问题、具有怎样的价值?效果如何衡量? 推荐系统诞生很早...

    CSDN技术头条
  • 利用Python进行录音和音频分析

    Python有个很强大的处理音频的库pyqudio, 使用pyaudio库可以进行录音,播放,生成wav文件等等。更多介绍可以查阅官方文档。

    林清猫耳
  • 不借助变量交换两个数

    我们在平时写代码的过程之中,竟然会有交换两个变量值的需求。然而我们大多数还是会采用借助额外变量的方式,因为这种方式不仅简单,容易理解,可读性高, 更重要的是适用...

    lucifer210
  • 棋牌游戏服务器架构: 详细设计(三) 数据库设计

    主要有3类Database: ServerInfoDB,UserInfoDB和GameDB。 ServerInfoDB主要存储的是游戏列表的信息,UserIn...

    李海彬
  • 棋牌游戏服务器架构: 详细设计(三) 数据库设计

    主要有3类Database: ServerInfoDB,UserInfoDB和GameDB。 ServerInfoDB主要存储的是游戏列表的信息,UserIn...

    李海彬
  • 棋牌游戏服务器架构: 详细设计(三) 数据库设计

    主要有3类Database: ServerInfoDB,UserInfoDB和GameDB。 ServerInfoDB主要存储的是游戏列表的信息,UserIn...

    李海彬
  • BZOJ 2257: [Jsoi2009]瓶子和燃料【数论:裴蜀定理】

    2257: [Jsoi2009]瓶子和燃料 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1326  Sol...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动