一、二叉树的节点和深度关系
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^2+2^1-(h-1)
F(N)=N-log(N+1)
通过与向上调整建堆,我们不难得到,这种情况下.向下调整建堆的效果更好.
三、堆的使用与堆排序
现在我们我思考如果我有这样的一个数组:
{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 (child+1 < 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;
}
}
而这种操作我们也称之为堆排序。