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:

(i) insert, which takes an integer (a key) and inserts it in the binomial heap. The method returns true, if the key is successfully inserted and false otherwise. In the case, if the array should be resized, use the method resizeArray (see below).

(ii) getMin, which returns the minimal key in binomial heap. The implementation will be also efficient if you iterate through the array. That is to say, you do not need to store a pointer to minimal key. If the binomial heap is empty, the method should return the maximal positive integer (Integer.MAX VALUE). 2

(iii) 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).

(iv) 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.

(v) merge, which merges two binomial trees (of the same size), and returns the merged binomial tree.

(vi) 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.

import java.util.Vector;

public class BinomialNode { public Vector childs; public int key; public BinomialNode(int key) { this.key = key; childs = new Vector(); } public boolean addChild(BinomialNode child) { return childs.add(child); } public Vector getChilds() { return this.childs; } public int getKey() { return this.key; } }

import java.util.Vector;

public class BinomialHeap { BinomialNode[] data; BinomialHeap(){ data = new BinomialNode[1]; } public boolean insert(int key) { throw new UnsupportedOperationException("need to be implemented"); } public int getMin() { throw new UnsupportedOperationException("need to be implemented"); } public boolean delMin() { throw new UnsupportedOperationException("need to be implemented"); } private void resizeArray() { throw new UnsupportedOperationException("need to be implemented"); } private BinomialNode merge(BinomialNode t1, BinomialNode t2) { throw new UnsupportedOperationException("need to be implemented"); } }