基本原理最大堆是一个二叉树,要求这个二叉树的父节点大于它的子节点,同时这个二叉树是一个完全二叉树,也就是说这个二叉树除了最底层之外的其它节点都应该被填满,最底层应该从左到右被填满。显然,最大堆的顶部节点的值是整个二叉树中最大的。我们使用数组来构建一个最大堆,使用数组构建一个二叉树最大堆存在如下性质。假设二叉树某节点在数组中的下标索引为index,则它的父节点在数组中的下标索引为parent = (index - 1) // 2,它的左子节点的下标索引为child_left = index * 2 + 1,右子节点的下标索引为child_right = index * 2 + 2。如果计算出来parent小于0或者child大于了数组最大值,就说明没有父节点或者子节点。代码实现接下来我们创建最大堆类,存储一些堆的基本信息以及工具方法1234567classHeap(object):def__init__(self) ->None:self._data = []def_size(self) ->int:returnlen(self._data)def_swap(self, i:int, j:int) ->None:self._data[i], self._data[j] = self._data[j], self._data[i]Heap类包含了三个方法,一个初始化方法创建了一个数组,
...
继续阅读
(216)