好资源导航 » 文章资讯 » python下实现二叉堆以及堆排序的示例

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

2023-09-23 22:10:06 107

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

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

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

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

看下代码：

#构建二叉堆
defbinaryHeap(arr,lenth,m):
temp=arr[m]#当前结点的值
while(2*m+1=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))

堆排序过程就是依次将最后的结点与首个节点进行对比交换：

#构建二叉堆
defbinaryHeap(arr,lenth,m):
temp=arr[m]#当前结点的值
while(2*m+1=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


defpop(arr):
first=arr.pop(0)
returnfirst


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封装了一个堆模块,我们使用该模块可以很高效的实现一个优先队列

importheapq


classItem:
def__init__(self,name):
self.name=name

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


classPriorityQueue:
def__init__(self):
self._queue=[]
self._index=0

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

defpop(self):
returnheapq.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下实现二叉堆以及堆排序的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

返回顶部
3162201930
czq8825@qq.com

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

热门推荐

随机推荐