当前位置:   article > 正文

Python中的大根堆_python 大根堆

python 大根堆

什么是大根堆

大根堆是一种完全二叉树,每个内部结点的值都大于或等于子结点的值,将堆的元素映射到数组中很简单:如果一个结点的下标是k,则其左孩子的下标为2k+1,右孩子的下标为2k+2。

大根堆的表示

可以将大根堆表示为数组,根结点为Arr[0]。对于一个下标为i的结点,即Arr[i],则Arr[(i-1)/2]为其父节点,Arr[(2*i)+1]返回左孩子结点,Arr(2*i)+2]返回右孩子结点。

大根堆的操作

1. getMax(): 返回大根堆的根结点,时间复杂度为O(1)。

2. extractMax():将堆顶元素去除,此操作的时间复杂度为O(Log n),因为此操作需要在除去根之后维护堆属性(通过调用heapify())。

3. insert():插入一个新的结点,时间复杂度为O(Log n),首先是将新结点加入到堆的最后,如果新结点比其父节点小,则不需要做任何操作,反之,需要向上回溯去维护大根堆的性质。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/707617
推荐阅读
相关标签
  

闽ICP备14008679号