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])

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

相关文章

python aiohttp的使用详解

python aiohttp的使用详解

1.aiohttp的简单使用(配合asyncio模块) import asyncio,aiohttp async def fetch_async(url): print(url)...

python 利用pyttsx3文字转语音过程详解

这篇文章主要介绍了python 利用pyttsx3文字转语音过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 # -*- c...

matplotlib设置legend图例代码示例

matplotlib设置legend图例代码示例

本文主要是关于matplotlib的一些基本用法。 Demo import matplotlib.pyplot as plt import numpy as np # 绘制普通图像...

浅谈pyqt5在QMainWindow中布局的问题

引言: 在pyqt5中使用了父类为QMainWindow的话,在里面使用布局类,QGridLayout, QHBoxLayout ,QVBoxLayout 时,发现不好用。 解决: 如果...

布同 Python中文问题解决方法(总结了多位前人经验,初学者必看)

因为Python是自带文档,可以通过help函数来查询每一个系统函数的用法解释说明。一般来说,关键的使用方法和注意点在这个系统的文档中都说的很清楚。我试图在网上找过系统文档的中文版的函数...