python中二叉堆的详细介绍(代码示例)

如果下载的源码需要作者授权,请更换源码。本站免费分享资源不会增加授权

本篇文章给大家带来的内容是关于python中二叉堆的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

一、堆

数据结构 堆(heap) 是一种优先队列。队列是一种先进先出的数据结构。队列的一个重要变种称为优先级队列。使用优先队列能够以任意顺序增加对象,并且能在任意的时间(可能在增加对象的同时)找到(也可能移除)最小的元素,也就是说它比python的min方法更加有效率。
在优先级队列中,队列中的项的逻辑顺序由它们的优先级确定。最高优先级项在队列的前面,最低优先级的项在后面。因此,当你将项排入优先级队列时,新项可能会一直移动到前面。

二、二叉堆操作

我们的二叉堆实现的基本操作如下:

BinaryHeap() 创建一个新的,空的二叉堆。
insert(k) 向堆添加一个新项。
findMin()返回具有最小键值的项,并将项留在堆中。
delMin() 返回具有最小键值的项,从堆中删除该项。
如果堆是空的,isEmpty() 返回true,否则返回 false。
size() 返回堆中的项数。
buildHeap(list) 从键列表构建一个新的堆。

注意,无论我们向堆中添加项的顺序是什么,每次都删除最小的。

为了使我们的堆有效地工作,我们将利用二叉树的对数性质来表示我们的堆。为了保证对数性能,我们必须保持树平衡。平衡二叉树在根的左和右子树中具有大致相同数量的节点,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 在我们的堆实现中,我们通过创建一个 完整二叉树 来保持树平衡。 一个完整的二叉树是一个树,其中 每层结点都完全填满,在最后一层上如果不是满的,则只缺少右边的若干结点。 Figure 1 展示了完整二叉树的示例。
完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。

# from pythonds.trees.binheap import BinHeap class BinHeap:     def __init__(self):         self.heapList = [0]         self.currentSize = 0     def insert(self,k):         '''将项附加到列表的末尾,并通过比较新添加的项与其父项,我们可以重新获得堆结构属性。 '''         self.heapList.append(k)         self.currentSize = self.currentSize + 1         self.percUp(self.currentSize)     def buildHeap(self, alist):         '''直接将整个列表生成堆,将总开销控制在O(n)'''         i = len(alist) // 2         self.currentSize = len(alist)         self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本         while (i > 0):             self.percDown(i)            i = i - 1     def percUp(self,i):         '''如果新添加的项小于其父项,则我们可以将项与其父项交换。'''         while i // 2 > 0:    # // 取整除 - 返回商的整数部分(向下取整)             if self.heapList[i] < self.heapList[i//2]:                tmp = self.heapList[i // 2]                self.heapList[i // 2] = self.heapList[i]                self.heapList[i] = tmp             i = i // 2     def percDown(self, i):         '''将新的根节点沿着一条路径“下沉”,直到比两个子节点都小。'''         while (i * 2) <= self.currentSize:             mc = self.minChild(i)             if self.heapList[i] > self.heapList[mc]:                 tmp = self.heapList[i]                 self.heapList[i] = self.heapList[mc]                 self.heapList[mc] = tmp             i = mc     def minChild(self, i):         '''在选择下沉路径时,如果新根节点比子节点大,那么选择较小的子节点与之交换。'''         if i * 2 + 1 > self.currentSize:             return i * 2         else:             if self.heapList[i * 2] < self.heapList[i * 2 + 1]:                 return i * 2             else:                 return i * 2 + 1     def delMin(self):         '''移走根节点的元素(最小项)后如何保持堆结构和堆次序'''         retval = self.heapList[1]         self.heapList[1] = self.heapList[self.currentSize]         self.currentSize = self.currentSize - 1         self.heapList.pop()         self.percDown(1)         return retval bh = BinHeap() bh.buildHeap([9,5,6,2,3]) print(bh.delMin()) print(bh.delMin()) print(bh.delMin()) print(bh.delMin()) print(bh.delMin())

关于二叉堆的最后一部分便是找到从无序列表生成一个“堆”的方法。我们首先想到的是,将无序列表中的每个元素依次插入到堆中。对于一个排好序的列表,我们可以用二分搜索找到合适的位置,然后在下一个位置插入这个键值到堆中,时间复杂度为O(logn)。另外插入一个元素到列表中需要将列表的一些其他元素移动,为新节点腾出位置,时间复杂度为O(n)。因此用insert方法的总开销是O(nlogn)。其实我们能直接将整个列表生成堆,将总开销控制在O(n)。Listing 6 所示的是生成堆的操作。

能在O(n)的开销下能生成二叉堆看起来有点不可思议,这里就不做证明了。但要理解用O(n)的开销能生成堆的关键是因为logn因子基于树的高度。而对于buildHeap里的许多操作,树的高度比logn要小。

本文由(壳先生)整理自网络,如转载请注明出处:https://www.mrshell.com;
本站发布的内容若侵犯到您的权益,请邮件联系 i@mrshell.com 删除,我们将及时处理!
===========================================================================

1. 本站大部分下载资源收集于网络,不保证其完整性以及安全性,请下载后自行测试。
2. 本站资源仅供学习和交流使用,版权归资源原作者所有,请在下载后24小时之内自觉删除。
3. 不得使用于非法商业用途,商用请支持正版!不得违反国家法律,否则后果自负!
4. 若作商业用途,请购买正版,由于未及时购买和付费发生的侵权行为,与本站无关。
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!

=================================================================

壳先生 » python中二叉堆的详细介绍(代码示例)

发表评论

提供最优质的资源集合

立即查看 了解详情