相思资源网 Design By www.200059.com
堆是一种特殊的树形结构， 堆中的数据存储满足一定的堆序。堆排序是一种选择排序， 其算法复杂度， 时间复杂度相对于其他的排序算法都有很大的优势。
堆分为大头堆和小头堆， 正如其名， 大头堆的第一个元素是最大的， 每个有子结点的父结点， 其数据值都比其子结点的值要大。小头堆则相反。
我大概讲解下建一个树形堆的算法过程:
找到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实现
相思资源网 Design By www.200059.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
相思资源网 Design By www.200059.com
暂无python下实现二叉堆以及堆排序的示例的评论...
苹果官宣WWDC 2024！预计会有大批AI功能 - 2024/11/16
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。