Consider a binomial heap where only insert and findmin operations are allowed (no extractmin). Show that...

Consider a binomial heap where only insert and findmin operations are allowed (no extractmin). Show that both of these operations can be done in amortized O(1) time. Hint: For findmin consider explicitely storing a pointer to the tree with minimum root and then update it during insert if needed. For insert, you’ll need to use amortization and develop a good potential function.

Solutions

Expert Solution

Solution: A binomial heap is actually nothing but a collection of min heaps. Since we know that in a min-heap, the minimum element is always present at the root node of the tree, therefore, the minimum element can always be found at the top of the tree in a constant amount of time that is O(1). It can be easily performed by traversing to the minimum root node of the tree which can be implemented using a pointer that is always pointing to the minimum key root of the binomial tree.

On, the other hand, the insertion in the tree has to be done at the leaves and hence the heapify algorithm has to be called within that heap of the binomial heap and hence it would take O(log N) of time where n is nothing but the level of the particular heap within the binomial heap and hence the insertion would take O(1) of time but the heapify would be called and it would take an additional O(log N) time.

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!

venereology answered 9 months ago

Next > < Previous

Related Solutions

We can build a heap by repeatedly calling the insert function to insert the elements into...

We can build a heap by repeatedly calling the insert function to insert the elements into the heap. Here is pseudocode: buildHeap(A) h = new empty heap for each element e in A h.insert(e) What is the Big-O runtime of this version of buildHeap? Justify your answer.

C++ Heap Tree: Make a program called "priority_queue" that has the following operations using a heap and...

C++ Heap Tree: Make a program called "priority_queue" that has the following operations using a heap and simulating a prioritized row of integers with higher priority value. I would appreciate if someone could help me with this code It has to include the following on the code: push Description: Add data to prioritized row Entry: An integer, which you want to add to the prioritized row Exit: Nothing Precondition: n is an integer Postcondition: The prioritized row contains new data. pop...

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap

This problem requires you to use a heap to store items, but instead of using a key of an item to determine where to store the item in the heap, you need to assign a priority (key) to each item that will determine where it is inserted in the heap 7a) Show how to assign priorities to items to implement a first-in, first-out queue with a heap. 7b) Show how to assign priorities to items to implement a first-in, last-out stack with...

Pretend that our galaxy is a heap of sand, where each grain of sand is a...

Pretend that our galaxy is a heap of sand, where each grain of sand is a star, that is about 10 inches across. Since the actual Milky Way is 100,000 light years across, you can act like each inch of your pile represents 10,000 light years. Describe your heap of sand mention how thick it is, how many grains of sand there will be, what it will look like, and what properties it would have.

Suppose you have a min-heap in an array a[] where: ● The root isstored at...

Suppose you have a min-heap in an array a[] where: ● The root is stored at index 1 ● There are 15 elements (in a[1]...a[15]) ● There are no duplicates (this is not true in general for heaps; but assume it is true for this problem). Fill in the blanks in the statements below; the resulting statement must be true for any heap obeying the above properties.There are/is at least ____6_______ elements in theheap that are/is larger than a[3] ""There...

Pretend that our galaxy is a heap of sand, where each grain of sand is a...

Pretend that our galaxy is a heap of sand, where each grain of sand is a star, that is about 10 inches across. Since the actual Milky Way is 100,000 light years across, you can act like each inch of your pile represents 10,000 light years. Describe your heap of sand. Be specific, in terms of how thick it is, how many grains of sand there are, what it looks like, what properties it has, etc.

Consider an almost-priority-queue data structure, which allows two operations: insert and extract almost min. extract almost...

Consider an almost-priority-queue data structure, which allows two operations: insert and extract almost min. extract almost min operation outputs either the first minimum or a second minimum item from the current structure (and doesn’t tell you which it outputted). Prove that not both these operations can be done in o(log n) time even if amortization is allowed.

Use the Heap class provided to implement a sort routine in a Main class where the...

Use the Heap class provided to implement a sort routine in a Main class where the user enters a series of values, each value is then pushed onto a heap, then the values are printed out in ascending order. public class Heap { public static final int SIZE = 1025; public Heap() { elt = new Element[SIZE]; lastLoc = 0; } public void push(String k, Object o) { if (!fullCheck()) { lastLoc++; elt[lastLoc] = new Element(k,o); int loc = lastLoc;...

Why are only odd harmonics allowed in a closed pipe?

Consider the four characteristics of a Binomial experiment . Give an example of a binomial experiment...

Consider the four characteristics of a Binomial experiment . Give an example of a binomial experiment in the real world (and how these characteristics are present), and its application to a business research problem

Subjects