书签 分享
• / 18
• 下载费用：10 金币

# 高级数据结构二项式堆分析

Analysis Of Binomial Heaps Operations • Insert § Add a new min tree to top-level circular list. • Meld § Combine two circular lists. • Remove min § Pairwise combine min trees whose roots have equal degree. § O(MaxDegree + s), where s is number of min trees following removal of min element but before pairwise combining. Binomial Trees • Bk , k 0, is two Bk-1s. • One of these is a subtree of the other. B1 B2 B3 B0 All Trees In Binomial Heap Are Binomial Trees • Insert creates a B0. • Meld does not create new trees. • Pairwise combine takes two trees of equal degree and makes one a subtree of the other. • Let n be the number of operations performed. § Number of inserts is at most n. § No binomial tree has more than n elements. § MaxDegree 2. § Meld = 1. § Remove min = 3log2n. • Show that P(i) – P(0) = 0 for all i. Potential Function • P(i) = amortizedCost(i) – actualCost(i) + P(i – 1) • P(i) – P(0) is the amount by which the first i operations have been over charged. • We shall use a credit scheme to show P(i) – P(0) = 0 for all i. • P(i) = number of credits after operation i. • Initially number of credits is 0. • P(0) = 0. Insert • Guessed amortized cost = 2. • Use 1 unit to pay for the actual cost of the insert. • Keep the remaining 1 unit as a credit for a future remove min operation. • Keep this credit with the min tree that is created by the insert operation. • Potential increases by 1, because there is an overcharge of 1. Meld • Guessed amortized cost = 1. • Use 1 unit to pay for the actual cost of the meld. • Potential is unchanged, because actual and amortized costs are the same. Remove Min • Let MinTrees be the set of min trees in the binomial heap just before remove min. • Let u be the degree of min tree whose root is removed. • Let s be the number of min trees in binomial heap just before pairwise combining. § s = #MinTrees + u – 1 • Actual cost of remove min is = 0 for all i. • Derive amortized cost of ith operation using DP = P(i) – P(i – 1) = amortized cost – actual cost • amortized cost = actual cost + DP Potential Function • P(i) = S#MinTrees(j) § #MinTrees(j) is #MinTrees for binomial heap j. § When binomial heaps A and B are melded, A and B are no longer included in the sum. • P(0) = 0 • P(i) = 0 for all i. • ith operation is an insert. § Actual cost of insert = 1 § DP = P(i) – P(i – 1) = 1 § Amortized cost of insert = actual cost + DP = 2 ith Operation Is A Meld • Actual cost of meld = 1 • P(i) = S#MinTrees(j) ·DP = P(i) – P(i – 1) = 0 • Amortized cost of meld = actual cost + DP = 1 ith Operation Is A Remove Min • old = value just before the remove min • new = value just after the remove min. • #MinTreesold(j) = value of #MinTrees in jth binomial heap just before this remove min. • Assume remove min is done in kth binomial heap. ith Operation Is A Remove Min • Actual cost of remove min from binomial heap k = 2log2n – 1 + #MinTreesold(k) ·DP = P(i) – P(i – 1) = S[#MinTreesnew(j) – #MinTreesold(j)] = #MinTreesnew(k) – #MinTreesold(k). • Amortized cost of remove min = actual cost + DP = 2log2n – 1 + #MinTreesnew (k) = 3log2n. 麦档网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
0条评论

## 当前资源信息 wh****0 ## 相关资源

• 中小学生抗击疫情自我心理辅导
• 中小学生命安全教育专题培训（预防溺水）
• 疫情期间学生心理辅导（如何正确认识自己的心境反应呢？）
• 青少年预防溺水课件班队会课件
• 疫情期间学生心理辅导（学生心理自助方法有哪些呢）
• 疫情期间学生心理辅导（防疫期间如何科学做好停课不停学）
• 疫情期间学生心理辅导（班队会课件）
• 青少年预防溺水（主题班会课件）
• 人教版七年级下册数学课件：9.1.1不等式及其解集(共15张PPT)
• 华师版七年级数学下册10.1.1生活中的轴对称课件（共29张PPT）
• 人教版七年级下册数学课件：8.2代入消元法解二元一次方程组(共15张PPT)
• ## 相关搜索

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群：3303921

麦档网为“文档C2C模式”，即用户上传的文档所得金币直接给(下载)用户，本站只是中间服务平台，本站所有文档下载所得的金币归上传人(含作者)所有。
川公网安备:51019002001290号

本站提供办公文档学习资料考试资料文档下载

收起
展开