python下实现二叉堆以及堆排序的示例_网络技术

python下实现二叉堆以及堆排序的示例

发布时间 - 2026-01-11 03:28:06 点击率：次

堆是一种特殊的树形结构，堆中的数据存储满足一定的堆序。堆排序是一种选择排序，其算法复杂度，时间复杂度相对于其他的排序算法都有很大的优势。

堆分为大头堆和小头堆，正如其名，大头堆的第一个元素是最大的，每个有子结点的父结点，其数据值都比其子结点的值要大。小头堆则相反。

我大概讲解下建一个树形堆的算法过程:

找到N/2 位置的数组数据，从这个位置开始，找到该节点的左子结点的索引，先比较这个结点的下的子结点，找到最大的那个，将最大的子结点的索引赋值给左子结点，然后将最大的子结点和父结点进行对比，如果比父结点大，与父节点交换数据。当然，我只是大概说了下实现，在此过程中，还需要考虑结点不存在的情况。

看下代码：

# 构建二叉堆 
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())

具体请看heapq官网

以上这篇python下实现二叉堆以及堆排序的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。

# 堆排序 # python实现 # 理解二叉堆数据结构及Swift的堆排序算法实现示例 # Java实现堆排序和图解 # Java实现堆排序（大根堆）的示例代码 # java编程实现优先队列的二叉堆代码分享 # 彻底搞定堆排序:二叉堆 # 小头 # 是一种 # 给大家 # 都有 # 第一个 # 在此 # 说了 # 其他的 # 很高 # 希望能 # 不存在 # 其名 # 还需要 # 这篇 # 相对于 # 首个 # 装了 # 都比 # 小编 # 官网

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：Linux下conda安装caffe与pb转caffe问题怎

下一篇：Android星级评分条的实现代码

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：Linux下conda安装caffe与pb转caffe问题怎

下一篇：Android星级评分条的实现代码