首页 > 代码库 > 堆
堆
堆是完全二叉树,一个大小为n的堆为一棵包含n个节点的完全二叉树。完全二叉树的根称为堆顶。当堆中每个节点的关键字值大于等于其双亲节点的关键字值,这样的堆称为最小堆,当子节点的值都小于等于其父节点时,称为最大堆。
使用数组来保存堆中元素。对于数组中的i节点,其子节点为 2i +1 和2i + 2。则由此可以轻松的判断节点之间的关系。然后我们考虑最小堆的具体情况。
然后考虑堆的向下调整运算AdjustDown(T heap[],int r,int j)。在堆中r+1 到 j 之间的元素都已满足最小堆的要求,然后加入元素r即heap[r],调整顺序,使得到的r 到 j中间的元素都满足要求。具体操作是将r与其子节点的值进行比较,若大于其左右孩子中的较小者,则与其交换,然后进行比较其与其新的孩子。直到r不大于其孩子或到达堆底。
建堆运算CreateHeap将一个以元素序列通过向下调整建成最小堆。调整从位置为(n-2)/2取整数部分(由于堆是一个完全二叉数,对于二叉树,有i节点的父节点为(i-1)/2取整数部分,则这里求的是n-1节点的父节点,也就是自底向上的第一个分支节点)的元素开始,然后重复调用AdjustDown操作,知道下标为0的元素调整完成,则建堆结束。
template <class T> void AdjustDown(T heap[],int r,int j){ T temp = heap[r]; int child = 2 * r + 1; while(child < j ){ child = heap[child] > heap[child+1] ? (child+1) : child; if(temp > heap[child]){ heap[r] = heap[child]; heap[child] = temp; r = child ; child = 2 * r + 1; temp = heap[r]; }else break; } } template <class T> void CreateHeap(T heap[],int n){ for(int i = n/2 - 1;i>-1;i--) AdjustDown(heap,i,n-1); } int main() { int A[7] = {99,36,68,72,12,48,02}; CreateHeap(A,7); return 0; }
每执行一次AdjustDown的时间为O(log2 n)。建堆的时间复杂度为O(n)。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。