网站开发实训的心得,青海公路建设服务网站,重庆建设工程信息网官网安全监督信息,做公司官网多少钱一、二叉树的节点和深度关系
1.满二叉树 我们可以假设二叉树有N个节点#xff0c;深度为h我们可以恒容易得到满二叉树每行的节点数#xff0c;然后错位相减,算出节点与高度的关系。 2.完全二叉树 注意我这个是因为最后一行的节点数为1。 二、向上调整建堆和向下调整建堆的时…一、二叉树的节点和深度关系
1.满二叉树 我们可以假设二叉树有N个节点深度为h我们可以恒容易得到满二叉树每行的节点数然后错位相减,算出节点与高度的关系。 2.完全二叉树 注意我这个是因为最后一行的节点数为1。 二、向上调整建堆和向下调整建堆的时间复杂度差异
1.向上调整建堆
现在我们有一个数组我们要让它向上调整建堆 我们知道时间复杂度考虑的是最坏情况现在我们来思考每一层向上调整需要的次数: 第一次不需要,第二层最多一次,以此类推,我们能退出以下关系式: 也就是: 2.向下调整建堆 我们可以想象一下:
深度为h时,第一层每个节点的最大调整次数时h-1
深度为h时,第二层每个节点的最大调整次数时h--2
深度为h时,第三层每个节点的最大调整次数时h--3
深度为h时,第四层每个节点的最大调整次数时h--4
以此类推,倒数第二层每个节点的最大调整次数为1
最后一层每个节点的最大调整次数为0 因此我们可以得到这样一个关于它的时间复杂度
F(h)2^(h-1)2^(h-2)*2.....2^3*(h-3)2^2*(h-2)2^1*(h-1)
我们可以通过错位相减法,可以得到。
F(h)2^(h-1)2^(h-2)2^(h-3)....2^22^1-(h-1)
F(N)N-log(N1) 通过与向上调整建堆,我们不难得到,这种情况下.向下调整建堆的效果更好. 三、堆的使用与堆排序
现在我们我思考如果我有这样的一个数组:
{0,3,1,4,6,9,2,7,5,8},如果我们要用堆让它完成一个升序的排列我们应该选择建大堆还是建小堆呢不少人可能会选择建小堆但是如果我们完成了小堆我们会发现 我们只取出了最小值很明显这种方法是不行的。
所以这里我们选择建大堆。
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){// 假设法选出左右孩子中小的那个孩子if (child1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void Swap(HPDataType* px, HPDataType* py)
{HPDataType tmp *px;*px *py;*py tmp;
}
void HeapSort(int* a, int n)
{for (int i (n-1-1)/2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
而这种操作我们也称之为堆排序。
