1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Elza [17]
3 years ago
11

Consider an ordinary binary heap data structure with n elements that supports the instructions Insert and Extract-Min in O(log n

) worst- case time. Give a potential function Φ such that the amortized cost of Insert is O(log n) and the amortized cost of Extract-Min is O(1), and show that it works.
Mathematics
1 answer:
Ierofanga [76]3 years ago
7 0

Answer:

It has been proved from the explanation below that the amortized cost of Insert is O(log n) and the amortized cost of Extract-Min is O(1),

Step-by-step explanation:

First of all, let's look at what "Extra-min" does;

It does the following ;

- Extract the root, (O1) actual time

- Replaces it with the last element x in the heap and repair the heap down or up.

- It takes O (Logn) time which is the depth of the heap.

Now, to get O(1) amortized time for extra-min, the last element "x" must have enough potential for repairing the heap and this potential must be in order of its depth.

Since we have K elements and so the weight of the kth element is WK in the heap as it's depth. So we can say;

WK = log k - - - - - - - - - eq (1)

Thus, the potential function Φ of the heap Hn for the n elements can be defined as ΦHn = Σ(WK) for k = 1 up till n. And so ΦHn will surely be greater than 0.

Thus; ΦHn = n(Logn)

Now let's check for insert ;

- pay actual cost of insert (logn)

-raise potential of the new elements

Now, using extra-min; O(1) amortized. To repair the heap, we'll use the potential of log(n) for the last element x as mentioned earlier.

In summary, when we use insert, potential increases and this can be afforded by paying insert more while when extra-min, potential decreases by a right moment of the cost of repairing.

Thus, we clearly see that Insert is O(log n) amortized and Extract-Min is O(1) amortized.

You might be interested in
At 19:30 Jack lights a campfire. At 22:15 he puts the fire out. Yeah
Evgen [1.6K]
Yeah because he Sheldon do I be j I got work y’all got work at
3 0
3 years ago
Cornelius has 25 nickels, 39 dimes, 22 quarters, and 12 fifty-cent pieces. How
Mars2501 [29]

Answer:

16.65$

Step-by-step explanation:

6 0
3 years ago
Need help on this becOuse I don't understand
joja [24]
Six pounds of rice is $18 homie

8 0
3 years ago
Read 2 more answers
Is Y equals 2.5 X proportional
Ivahew [28]

Answer:

no but 1+1=2 hehe

Step-by-step explanation:

follow me on tt: dxddy.drip0

6 0
3 years ago
Linda received the following scores on her essay tests.
muminat
The answer is 65 if your wondering why you have to put the numbers from least to greatest then find the one that is in the middle

8 0
3 years ago
Other questions:
  • 5% of what number is 65
    11·1 answer
  • Mary is making some shirts for her school drama department the fabric has 3 1/6 yards of the fabric she wants in stock but this
    11·1 answer
  • Suppose the population of a town is 15,200 and is growing 2% each year. Write an equation to model the population growth. Predic
    10·2 answers
  • Joanna went to the farmers market to buy some apples and oranges. She bought 8 oranges and some apples. The cost per orange was
    10·1 answer
  • Y less than x minus 4
    11·1 answer
  • Explain Well please.
    9·1 answer
  • Which number is greatest?
    5·2 answers
  • There is a bag filled with 6 blue and 5 red marbles.
    13·1 answer
  • A van travels 150 miles on 6 gallons of gas. How many gallons will it need to travel 325 miles?
    15·1 answer
  • 5(-2/3)= what is the anwser to this
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!