• / 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条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:高级数据结构二项式堆分析
链接地址:https://www.maidoc.com/p-15695384.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

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

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

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


收起
展开