22 O-3个 清华大学宋域恒 请华大学宋斌 Properties Proof of the properties For binomial tree B: All by induction, because it is defined 1. There are 2k nodes recursively. Here we omit the proof. 2. The height of the tree is k 3. There are exactly (,)nodes at depth i for i=0, 1, 2,- k ·课堂练习 4. The root has degree k, which is greater than that of any other node; moreover if the children of the root e numbered from left to right by k-1, k-2,--, 2, 1,0, 清华大学末斌恒 请华大学宋恒 第三条性质的证明 Binomial heaps a binomial heaps H is a set of binomial D(k,i)=D(k-1,)+D(k-1,i-1) trees that satisfies the following binomial- heap properties Min-heap property: each tree in H obey the in-heap property, which means that the key of each node is great than or equal to its parent or any k there exists at most one Bk in H. 清华大学末破恒 请华大学宋2 清华大学 宋斌恒 7 B0 B1 B2 B3 0 1 2 3 Depth 清华大学 宋斌恒 8 清华大学 宋斌恒 9 Properties • For binomial tree Bk: 1. There are 2k nodes. 2. The height of the tree is k 3. There are exactly (k i ) nodes at depth i for i=0,1,2,…,k 4. The root has degree k, which is greater than that of any other node; moreover if the children of the root are numbered from left to right by k-1,k-2,…,2,1,0, child i is the root of subtree Bi . 清华大学 宋斌恒 10 Proof of the properties • All by induction, because it is defined recursively. Here we omit the proof. • 课堂练习 清华大学 宋斌恒 11 第三条性质的证明 清华大学 宋斌恒 12 Binomial heaps • A binomial heaps H is a set of binomial trees that satisfies the following binomial￾heap properties: – Min-heap property: each tree in H obey the min-heap property, which means that the key of each node is great than or equal to its parent key – For any k there exists at most one Bk in H