Python heapq模块中heappush与heapify的使用详解

桃夭

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

原创

本文详细讲解Python中创建堆的两种基本方法：heappush()和heapify()。通过具体代码实例展示如何向堆中插入元素并保持堆性质，以及如何在已有数据列表上高效构建堆。同时扩展介绍了最小堆与最大堆的定义、节点下沉操作及完全二叉树的存储特性，帮助开发者深入理解Python堆数据结构的实现原理。

1、说明

在Python中，构建堆结构主要依赖两种核心方法：heappush() 和 heapify()。

使用 heappush() 方法时，随着新元素的不断加入，堆的有序性质（即堆特性）会被自动维持。

若数据已经存在于内存列表中，采用 heapify() 方法可以更高效地重新排列元素以构建堆。

2、实例


import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
 
heap = []
print('random :', data)
print()
 
for n in data:
  print('add {:>3}:'.format(n))
  heapq.heappush(heap, n)
  show_tree(heap)
   
# output
# random : [19, 9, 4, 10, 11]
#
# add 19:
#
#         19
# ------------------------------------
#
# add  9:
#
#         9
#     19
# ------------------------------------
#
# add  4:
#
#         4
#     19        9
# ------------------------------------
#
# add 10:
#
#         4
#     10        9
#   19
# ------------------------------------
#
# add 11:
#
#         4
#     10        9
#   19    11
# ------------------------------------

知识点扩展：

创建最大（小）堆

二叉堆在物理上表现为完全二叉树，其存储方式并非链式结构，而是采用顺序存储（通常基于数组）。

堆的基本操作包括插入和删除：插入时，新元素作为叶子节点并向上调整位置；删除时，通常移除堆顶元素后，剩余元素向下调整。

堆的构建过程涉及非叶子节点的向下调整，具体是从最后一个非叶子节点开始执行下沉操作。

最小堆：

在最小堆中，任意父节点的值均小于或等于其左右子节点的值。

构建最小堆的过程为：若非叶子节点的值大于其子节点，则将该节点向下交换（下沉）。

最大堆：

在最大堆中，任意父节点的值均大于或等于其左右子节点的值。

构建最大堆的过程为：若非叶子节点的值小于其子节点，则将该节点向下交换（下沉）。

到此这篇关于python创建堆的方法实例讲解的文章就介绍到这了,更多相关python创建堆的方法有哪些内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！