(In java) In this task, a binomial heap should be implemented. A binomial heap is implemented by an array with its elements being binomial trees: on the first place there is the binomial tree B0 with one element, on the second place there is the binomial tree B1 with two elements, on the third place there is the binomial tree B2 with four elements,. . . Each binomial tree is implemented recursively using the class BinomialNode. In this class there is nothing to implement. Methods in this class are needed for the implementation of the methods in the class BinomialHeap. More precisely, in the class BinomialHeap you should implement the following methods: -> delMin, which deletes the minimal key from the binomial heap. The method returns true, if the minimal key is successfully deleted and false otherwise (if the binomial heap is empty). -> resizeArray, which extends the array. The method is needed, for example, when you find out that you need an extra place in your array when inserting new element. Hint: Construct new array which is of double size and rewrite old elements in the new array. -> merge, which merges two binomial trees (of the same size), and returns the merged binomial tree. -> It might be a good idea to implement a method for merging two binomial heaps – it can than be used in implementation of insertion and deletion. But it is not necessary.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

(In java) In this task, a binomial heap should be implemented. A binomial heap is implemented by
an array with its elements being binomial trees: on the first place there is the binomial tree
B0 with one element, on the second place there is the binomial tree B1 with two elements,
on the third place there is the binomial tree B2 with four elements,. . . Each binomial tree
is implemented recursively using the class BinomialNode. In this class there is nothing to
implement. Methods in this class are needed for the implementation of the methods in the
class BinomialHeap. More precisely, in the class BinomialHeap you should implement the
following methods:
-> delMin, which deletes the minimal key from the binomial heap. The method returns
true, if the minimal key is successfully deleted and false otherwise (if the binomial
heap is empty).
-> resizeArray, which extends the array. The method is needed, for example, when
you find out that you need an extra place in your array when inserting new element.
Hint: Construct new array which is of double size and rewrite old elements in the
new array.
-> merge, which merges two binomial trees (of the same size), and returns the merged
binomial tree.
-> It might be a good idea to implement a method for merging two binomial heaps – it
can than be used in implementation of insertion and deletion. But it is not necessary.

The base is given for BinomialHeap:

import java.util.Vector;

public class BinomialHeap {
BinomialNode[] data;

BinomialHeap(){
data = new BinomialNode[1];
}

public boolean delMin() {

}

private void resizeArray() {

}

private BinomialNode merge(BinomialNode t1, BinomialNode t2) {

}
}

For BinomialNode:

import java.util.Vector;
public class BinomialNode {
public Vector<BinomialNode> childs;
public int key;

public BinomialNode(int key) {
this.key = key;
childs = new Vector<BinomialNode>();
}

public boolean addChild(BinomialNode child) {
return childs.add(child);
}

public Vector<BinomialNode> getChilds() {
return this.childs;
}

public int getKey() {
return this.key;
}

}Also It needs to run the following public tests:

public class PublicTests extends TestCase {
BinomialHeap heap;
int cmpsAtStart;
int cmpsAtEnd;

protected void setUp() throws Exception {
heap = new BinomialHeap();
}

public void testInsert() {
heap.insert(2);
assertEquals(2, heap.data[0].getKey());
}

public void testResize() {
heap.insert(7);
heap.insert(2);
assertEquals(4, heap.data.length);
}

public void testMerge() {
heap.insert(7);
heap.insert(2);
assertEquals(2, heap.data[1].getKey());
assertEquals(7, heap.data[1].getChilds().elementAt(0).getKey());
}

public void testNegativeNumbers() {
heap.insert(-17);
heap.insert(-32);
assertEquals(-32, heap.getMin());
assertEquals(-17, heap.data[1].getChilds().elementAt(0).getKey());
}

public void testGetMin() {
heap.insert(-17);
heap.insert(-32);
heap.insert(7);
heap.insert(22);
heap.insert(-7);
heap.insert(26);
assertEquals(-32, heap.getMin());
}

public void testDelMin() {
heap.insert(-17);
heap.insert(-32);
heap.insert(7);
heap.insert(22);
heap.insert(-7);
heap.insert(26);
assertEquals(-32, heap.getMin());
assertTrue(heap.delMin());
assertEquals(-17, heap.getMin());
}
}

Expert Solution

Step by step

Solved in 4 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.