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

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 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 = log2n. Complexity of remove min is O(log n + s) = O(n). Aggregate Method Get a good bound on the cost of every sequence of operations and divide by the number of operations. Results in same amortized cost for each operation, regardless of operation type. Can’t use this method, because we want to show a different amortized cost for remove mins than for inserts and melds. Aggregate Method – Alternative Get a good bound on the cost of every sequence of remove mins and divide by the number of remove mins. Consider the sequence insert, insert, …, insert, remove min. The cost of the remove min is O(n), where n is the number of operations in the sequence. So, amortized cost of a remove min is O(n/1) = O(n). Accounting Method Guess the amortized cost. Insert = 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