Potential of a binomial queue

Assignment Help Basic Computer Science

Reference no: EM13968358

1. Show that the binomial queues actually support merging in O(1) amortized time. De?ne the potential of a binomial queue to be the number of trees plus the rank of the largest tree.

2. Suppose that in an attempt to save time, we splay on every second tree operation. Does the amortized cost remain logarithmic?

3. Using the potential function in the proof of the splay tree bound, what is the maximum and minimum potential of a splay tree? By how much can the potential function decrease in one splay? By how much can the potential function increase in one splay? You may give Big-Oh answers.

Reference no: EM13968358

Questions Cloud

Deletion procedure for red-black trees : Modify the splay tree to support queries for the kth smallest item. Compare, empirically, the simpli?ed top-down splay with the originally described top-down splay. Write the deletion procedure for red-black trees.

What was role of railroads in the settlement of great west : What was the role of the railroads in the settlement of the Great West? What factors account for the rise of the American steel industry in the late nineteenth century?

Maximum value of the potential function : As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node's depth as a potenti..

What was remarkable about the american west : What was remarkable about the American West in the late 1800s? Describe the situation facing the Chinese in California in the late 1800s.

Potential of a binomial queue : 1. Show that the binomial queues actually support merging in O(1) amortized time. De?ne the potential of a binomial queue to be the number of trees plus the rank of the largest tree. 2. Suppose that in an attempt to save time, we splay on every secon..

Discuss how the federal government views marijuana use : Discuss how the federal government views/policies marijuana use. Also discuss any large legal cases that involved marijuana.

Consecutive insertions into a binomial queue : 1. When do M consecutive insertions into a binomial queue take less than 2M time units? 2. Suppose a binomial queue of N = 2k - 1 elements is built. Alternately perform M insert and deleteMin pairs. Clearly, each operation takes O(log N) time. Why do..

Write paper on drug addictions : Write a 5 page paper on drug addictions for my psychology class

Elements in the current row and column : The value of the selected position is added to the player's score, and that position becomes the current position and cannot be selected again. Players alternate until all grid elements in the current row and column are already selected, at which ..

User Account

All Pages