赞
踩
大根堆是一种完全二叉树,每个内部结点的值都大于或等于子结点的值,将堆的元素映射到数组中很简单:如果一个结点的下标是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),首先是将新结点加入到堆的最后,如果新结点比其父节点小,则不需要做任何操作,反之,需要向上回溯去维护大根堆的性质。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。