python下实现二叉堆以及堆排序的示例
堆是一种特殊的树形结构,堆中的数据存储满足一定的堆序。堆排序是一种选择排序,其算法复杂度,时间复杂度相对于其他的排序算法都有很大的优势。
堆分为大头堆和小头堆,正如其名,大头堆的第一个元素是最大的,每个有子结点的父结点,其数据值都比其子结点的值要大。小头堆则相反。
我大概讲解下建一个树形堆的算法过程:
找到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下实现二叉堆以及堆排序的示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持毛票票。