Python heapq使用详解及实例代码

yipeiwu_com5年前Python基础

 Python heapq 详解

Python有一个内置的模块,heapq标准的封装了最小堆的算法实现。下面看两个不错的应用。

小顶堆(求TopK大)

话说需求是这样的: 定长的序列,求出TopK大的数据。

import heapq
import random

class TopkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def TopK(self):
    return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]

if __name__ == "__main__":
  print "Hello"
  list_rand = random.sample(xrange(1000000), 100)
  th = TopkHeap(3)
  for i in list_rand:
    th.Push(i)
  print th.TopK()
  print sorted(list_rand, reverse=True)[0:3]

大顶堆(求BtmK小)

这次的需求变得更加的困难了:给出N长的序列,求出BtmK小的元素,即使用大顶堆。

算法实现的核心思路是:将push(e)改为push(-e)、pop(e)改为-pop(e)。

class BtmkHeap(object):
  def __init__(self, k):
    self.k = k
    self.data = []

  def Push(self, elem):
    # Reverse elem to convert to max-heap
    elem = -elem
    # Using heap algorighem
    if len(self.data) < self.k:
      heapq.heappush(self.data, elem)
    else:
      topk_small = self.data[0]
      if elem > topk_small:
        heapq.heapreplace(self.data, elem)

  def BtmK(self):
    return sorted([-x for x in self.data])

 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

相关文章

pygame实现简易飞机大战

利用pygame实现了简易版飞机大战。源代码如下: # -*- coding:utf-8 -*- import pygame import sys from pygame.local...

详解pyenv下使用python matplotlib模块的问题解决

详解pyenv下使用python matplotlib模块的问题解决

先来描述一下我遇到的问题,在进行matplotlib学习时, plot.show() 总是无法成功运行,总是会报一个错: RuntimeError: Python is not ins...

Python实现简单过滤文本段的方法

本文实例讲述了Python实现简单过滤文本段的方法。分享给大家供大家参考,具体如下: 一、问题: 如下文本: ## Alignment 0: score=397.0 e_value=...

Python完成毫秒级抢淘宝大单功能

Python完成毫秒级抢淘宝大单功能

引言 年中购物618大狂欢开始了,各大电商又开始了大力度的折扣促销,我们的小胖又给大家谋了一波福利,淘宝APP直接搜索:小胖发福利,每天领取三次粉丝专属现金大红包。 有了现金大红包,如...

python实现八大排序算法(2)

python实现八大排序算法(2)

本文接上一篇博客python实现的八大排序算法part1,将继续使用python实现八大排序算法中的剩余四个:快速排序、堆排序、归并排序、基数排序 5、快速排序 快速排序是通常被认为在同...