Python实现二叉堆与堆排序详解

宋时安

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

原创

本文详细介绍如何在Python中实现二叉堆及堆排序算法。内容涵盖大顶堆与小顶堆的概念、建堆过程（从N/2位置开始调整）、排序逻辑（首尾节点交换），并展示了基于Python标准库heapq模块构建高效优先队列的方法与代码示例。

堆是一种特殊的树形结构，其存储的数据需满足特定的堆序性质。堆排序作为一种选择排序算法，在算法复杂度和时间效率方面，相较于其他常见排序算法具有显著优势。

根据堆序性质，堆可分为大顶堆和小顶堆。大顶堆中，根节点（第一个元素）的值最大，且任意父节点的值均不小于其子节点的值；小顶堆则相反，根节点值最小，父节点值不大于子节点值。

以下简要说明构建二叉堆的算法流程：

首先定位到数组中索引为位置的元素，从此位置开始向下调整。对于当前节点，先比较其左右子节点，选出值较大的子节点索引（若左子节点存在且小于右子节点，则指向右子节点）。接着将该较大子节点与父节点比较，若子节点值大于父节点，则交换两者数据。需注意处理子节点不存在的情况。

具体实现代码如下：

# 构建二叉堆 
def binaryHeap(arr, lenth, m): 
 temp = arr[m] # 当前结点的值 
 while(2*m+1 < lenth): 
 lchild = 2*m+1 
 if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]: 
 lchild = lchild + 1 
 if temp < arr[lchild]: 
 arr[m] = arr[lchild] 
 else: 
 break 
 m = lchild 
 arr[m] = temp 
 
 
def heapsort(arr, length): 
 i = int(len(arr)/2) 
 while(i >= 0): 
 binaryHeap(arr, len(arr), i) 
 i = i - 1 
 
 print("二叉堆的物理顺序为:") 
 print(arr) # 输出二叉堆的物理顺序 
 
 
if __name__ == '__main__': 
 arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] 
 
 heapsort(arr, len(arr))

堆排序的核心过程是依次将数组末尾节点与首节点进行对比并交换，随后重新调整堆结构：

# 构建二叉堆
def binaryHeap(arr, lenth, m):
  temp = arr[m] # 当前结点的值
  while(2*m+1 < lenth):
    lchild = 2*m+1
    if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
      lchild = lchild + 1
    if temp < arr[lchild]:
      arr[m] = arr[lchild]
    else:
      break
    m = lchild
  arr[m] = temp


def heapsort(arr, length):
  i = int(len(arr)/2)
  while(i >= 0):
    binaryHeap(arr, len(arr), i)
    i = i - 1

  print("二叉堆的物理顺序为:")
  print(arr) # 输出二叉堆的物理顺序

  i = length-1
  while(i > 0):
    arr[i], arr[0] = arr[0], arr[i] # 变量交换
    binaryHeap(arr, i, 0)
    i = i - 1560


def pop(arr):
  first = arr.pop(0)
  return first


if __name__ == '__main__':
  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]

  heapsort(arr, len(arr))

  print("堆排序后的物理顺序")
  print(arr) # 输出经过堆排序之后的物理顺序

  data = pop(arr)
  print(data)

  print(arr)

Python标准库中封装了模块，利用该模块可以高效地实现优先队列功能。

import heapq


class Item:
  def __init__(self, name):
    self.name = name

  def __repr__(self):
    return 'Item({!r})'.format(self.name)


class PriorityQueue:
  def __init__(self):
    self._queue = []
    self._index = 0

  def push(self, item, priority):
    heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组
    self._index += 1

  def pop(self):
    return heapq.heappop(self._queue)[-1] # 逆序输出


if __name__ == '__main__':
  p = PriorityQueue()
  p.push(Item('foo'), 1)
  p.push(Item('bar'), 5)
  p.push(Item('spam'), 4)
  p.push(Item('grok'), 1)

  print(p.pop())
  print(p.pop())

更多关于模块的详细信息，请参阅官方文档。

以上即为Python实现二叉堆及堆排序的完整示例，希望能为读者提供参考，欢迎支持本站。