文章目录
一.定义一个Array-based MaxHeap
class MaxHeap{
private:
int size;
int n;
int* Heap;
void siftdown(int);
void siftup(int);
public:
void BuildHeapDown();
void BuildHeapUp();
bool RemoveMax();
bool isleaf(int pos){
return (pos > (n/2 - 1));
}
int parent(int pos){
return floor((pos-1)/2);
}
}
二. 使用siftdown构建BuildHeap
void MaxHeap::siftdown(int pos){
while(!isleaf(pos)){
int j = 2*pos+1;
int rc = 2*pos+2;
if(Heap(j) < Heap(rc)) j = rc; //取两子之大
if(Heap[pos] < Heap[j]){ //如果pos处值小于子值，那么调换位置
int temp = Heap[j];
Heap[j] = Heap[pos];
Heap[pos] = temp;
pos = j; //继续向下比较
}
}
}
void MaxHeap::BuildHeapDown(){
//对于非叶子结点，从最后一个节点开始往前依次进行siftdown
for(int i = (n/2 - 1); i>=0; i--) siftdown(i);
}
时间复杂度: 假设现在有一个满二叉树，node数量为
n
n
n, 最差情况下的时间复杂度为
∵
T
n
=
∑
i
=
1
log
(
n
+
1
)
(
log
(
n
+
1
)
−
i
)
∗
2
i
−
1
\because Tn = \sum_{i=1}^{\log (n+1)} {\left( \log (n+1) -i\right)} *{2}^{i-1}
∵Tn=i=1∑log(n+1)(log(n+1)−i)∗2i−1
令d = log(n+1),展开之后利用错位相减法可以求出
T
n
=
n
+
1
2
\text{令d = log(n+1),展开之后利用错位相减法可以求出 }Tn=\frac{n+1}{2}
令d = log(n+1),展开之后利用错位相减法可以求出 Tn=2n+1
∴
T
n
=
O
(
n
)
\therefore Tn = O(n)
∴Tn=O(n)
三. 使用siftup构建BuildHeap
void MaxHeap::siftup(int pos){
while(pos!=0){//只要不是root，都和自己的parent比较
if(Heap[pos] > Heap[parent(pos)]){
int temp = Heap[pos];
Heap[pos] = Heap[parent(pos)];
Heap[parent(pos)] = temp;
pos = parent(pos); //继续向上比较
}
}
}
void MaxHeap::BuildHeapUp(){
for(int i = 1; i<n; i++) siftup(i); // 从第二行开始，逐个进行siftup
}
时间复杂度: 假设现在有一个满二叉树，node数量为
n
n
n, 最差情况下的时间复杂度为
∵
T
n
=
∑
i
=
1
log
n
2
i
⋅
i
\because Tn = \sum_{i=1}^{\log n} {2}^{i} ·i
∵Tn=i=1∑logn2i⋅i
∴
T
n
=
O
(
n
log
n
)
\therefore Tn = O(n{\log n})
∴Tn=O(nlogn)
四.综合分析
（一）时间复杂度方面
首先，我们通过分析，分别计算出了两种建堆方式的时间复杂度。通过计算结果，我们看出通过
s
i
f
t
d
o
w
n
siftdown
siftdown来进行建堆的时间复杂度更低，为
O
(
n
)
O(n)
O(n)。
其实，从直观角度也可以得到这一结论。首先，我们要明确一点：节点数量随着深度增加是呈指数级增长的，而随着深度的加深，
B
u
i
l
d
H
e
a
p
D
o
w
n
BuildHeapDown
BuildHeapDown的调用时间是逐渐变低的。而
B
u
i
l
d
H
e
a
p
U
p
BuildHeapUp
BuildHeapUp的调用时间则会逐渐增加，所以根据
T
=
∑
i
=
1
n
T
i
m
e
(
i
)
T = \sum_{i=1}^{n} Time(i)
T=∑i=1nTime(i)我们也可以得出
B
u
i
l
d
H
e
a
p
D
o
w
n
BuildHeapDown
BuildHeapDown的时间复杂度更低。
（二）对于实现ADT方面
我们采用 s i f t d o w n siftdown siftdown是更有利于其他算法的实现的。比如在进行 R e m o v e M a x RemoveMax RemoveMax操作的时候，只需要将root节点和末尾节点换位并修改 n = n − 1 n=n-1 n=n−1，然后进行 s i f t d o w n siftdown siftdown就可以了。只需要 O ( log n ) O(\log n) O(logn)的时间；
bool MaxHeap::RemoveMax(int &t){
if(n==0) return false;
t = Heap[0]; //保存max
Heap[0] = Heap[--n]
Heap[n] = t;
if(n!=0) siftdown(0);
return true;
}