Python heapq模块详解：利用最小堆与最大堆高效求解TopK与BtmK问题

周末不加班

发布时间：2026-10-13| 3人浏览过

原创

本文详解Python内置heapq模块，通过构建TopkHeap和BtmkHeap类，演示如何利用最小堆求序列中最大的K个元素，以及通过取反技巧利用最小堆模拟最大堆来求最小的K个元素。

Python heapq 详解

Python标准库中内置了heapq模块，该模块对最小堆（min-heap）的算法进行了封装。接下来我们将通过两个典型应用场景来展示其用法。

小顶堆（求TopK大）

假设有一个具体的需求：给定一个定长的序列，需要从中找出数值最大的前K个数据（即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的序列，需要找出数值最小的前K个元素（即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])

感谢阅读，希望本文的内容能对大家有所帮助，也感谢大家对本站的支持！