This is in Java. You can reuse the code the code at http://users.cis.fiu.edu/~weiss/dsaajava3/code/BinomialQueue.java

The packaging division at Complex Circuits Inc. is assigned the task of packing integrated circuit chips into boxes for shipment. Boxes come in different sizes and the capacity of a box (in terms of number of chips) is an exponent of 2, i.e., boxes can hold 1, 2, 4, 8, 16.chips. Each chip has the following parameters:

weight a positive, real number in the range of 0-1

id positive integer in the range of 1000-9999

priority a positive integer in the range of 1-100

Boxes carrying chips arrive on the production line at the end of each hour in lots. The maximum number of chips that can be produced in each lot is 128. The software developer for the packaging division plans to use a binomial queue to represent the data structure for the chips, boxes and lots - each lot corresponds to a binomial queue, each box corresponds to a binomial tree and each chip corresponds to a node in the binomial tree.

Write a program in Java that does the following:

Input:

input the number of lots

randomly generate a number in the range of 1-128, to denote the number of chips produced in each lot; instantiate the chip object for each chip

for each lot, insert each chip object into a binomial queue, using the priority parameter as the key. Make sure that you satisfy the heap order property while creating the binomial queue. You should randomly generate each chip's parameters within the prescribed range, when you instantiate the chip object

deleteMin(int lot): deletes the chip with the minimum key in the lot (remember to adjust nodes after the delete to restore the binomial queue structure)

levelOrder(int lot): prints the level order traversal of each binomial tree in the binomial queue corresponding to the parameter lot. Nodes within each level should be put inside square brackets while printing; each node's (chip's) parameters should be put inside curly braces. (see sample I/O below)

Finally, you need to write a user interface for the program. Sample input and output are given below:

> Enter the number of lots in this production: 3

Randomly generating number of chips in each lot...

Lot 1: 7

Lot 2: 23

Lot 3: 4

Generating the chips for each lot:

Lot 1, Chip 1: {0.2, 3425, 14}

Lot 1, Chip 2: {0.7, 1298, 7}

Lot 1, Chip 3: {0.9, 1389, 15}

Lot 1, Chip 4: {0.3, 1929, 35}

Lot 1, Chip 5: {0.5, 9526, 92}

Lot 1, Chip 6: {0.1, 1748, 5}

Lot 1, Chip 7: {0.2, 7284, 51}

Lot 2, Chip 1: {0.5, 1357, 45}

Lot 2, Chip 23: {0.7, 3313, 39}

Lot 3, Chip 1: {0.7, 3313, 39}

Lot 3, Chip 4: {0.4, 7163, 27}

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 2

> Enter the lot number: 1

> Printing level order traversal of lot 1:

Box 1: [{0.2, 7284, 51}]

Box 2: [{0.1, 1748, 5}] [{0.5, 9526, 92}]

Box 3: [{0.7, 1298, 7}] [{0.2, 3425, 14} {0.9, 1389, 15}] [{0.3, 1929, 35}]

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 1

> Enter the lot number: 1

> Deleted minimum priority chip: {0.1, 1748, 5}

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 2

> Enter the lot number: 1

> Printing level order traversal of lot 1:

Box 1:

Box 2: [{0.2, 7284, 51}] [{0.5, 9526, 92}]

Box 3: [{0.7, 1298, 7}] [{0.2, 3425, 14} {0.9, 1389, 15}] [{0.3, 1929, 35}]

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 3

Bye!

Again, feel free to reuse the code at http://users.cis.fiu.edu/~weiss/dsaajava3/code/BinomialQueue.java

I got till here...

// BinomialQueue class // // CONSTRUCTION: with no parameters or a single item // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // Comparable deleteMin( )--> Return and remove smallest item // Comparable findMin( ) --> Return smallest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // vod merge( rhs ) --> Absord rhs into this heap // ******************ERRORS******************************** // Throws UnderflowException as appropriate

/** * Implements a binomial queue. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */ import java.util.Random; import java.util.Scanner;

public final class bqueue { /** * Construct the binomial queue. */ public bqueue() { theTrees = new BinNode[DEFAULT_TREES]; makeEmpty(); }

/** * Construct with a single item. */ public bqueue(int item) { currentSize = 1; theTrees = new BinNode[1]; theTrees[0] = new BinNode(item, null, null); }

private void expandTheTrees(int newNumTrees) { BinNode[] old = theTrees; int oldNumTrees = theTrees.length;

theTrees = new BinNode[newNumTrees]; for (int i = 0; i < Math.min(oldNumTrees, newNumTrees); i++) theTrees[i] = old[i]; for (int i = oldNumTrees; i < newNumTrees; i++) theTrees[i] = null; }

/** * Merge rhs into the priority queue. rhs becomes empty. rhs must be * different from this. * * @param rhs * the other binomial queue. */ public void merge(bqueue rhs) { if (this == rhs) // Avoid aliasing problems return;

currentSize += rhs.currentSize;

if (currentSize > capacity()) { int newNumTrees = Math.max(theTrees.length, rhs.theTrees.length) + 1; expandTheTrees(newNumTrees); }

BinNode carry = null; for (int i = 0, j = 1; j <= currentSize; i++, j *= 2) { BinNode t1 = theTrees[i]; BinNode t2 = i < rhs.theTrees.length ? rhs.theTrees[i] : null;

int whichCase = t1 == null ? 0 : 1; whichCase += t2 == null ? 0 : 2; whichCase += carry == null ? 0 : 4;

switch (whichCase) { case 0: /* No trees */ case 1: /* Only this */ break; case 2: /* Only rhs */ theTrees[i] = t2; rhs.theTrees[i] = null; break; case 4: /* Only carry */ theTrees[i] = carry; carry = null; break; case 3: /* this and rhs */ carry = combineTrees(t1, t2); theTrees[i] = rhs.theTrees[i] = null; break; case 5: /* this and carry */ carry = combineTrees(t1, carry); theTrees[i] = null; break; case 6: /* rhs and carry */ carry = combineTrees(t2, carry); rhs.theTrees[i] = null; break; case 7: /* All three */ theTrees[i] = carry; carry = combineTrees(t1, t2); rhs.theTrees[i] = null; break; } }

for (int k = 0; k < rhs.theTrees.length; k++) rhs.theTrees[k] = null; rhs.currentSize = 0; }

/** * Return the result of merging equal-sized t1 and t2. */ private BinNode combineTrees(BinNode t1, BinNode t2) { if (t1.element > t2.element) return combineTrees(t2, t1); t2.nextSibling = t1.leftChild; t1.leftChild = t2; return t1; }

/** * Insert into the priority queue, maintaining heap order. This * implementation is not optimized for O(1) performance. * * @param x * the item to insert. */ public void insert(int x) { merge(new bqueue(x)); }

/** * Find the smallest item in the priority queue. * * @return the smallest item, or throw UnderflowException if empty. */ public int findMin() { if (isEmpty()) return -1;// throw new UnderflowException( );

return theTrees[findMinIndex()].element; }

/** * Find index of tree containing the smallest item in the priority queue. * The priority queue must not be empty. * * @return the index of tree containing the smallest item. */ private int findMinIndex() { int i; int minIndex;

for (i = 0; theTrees[i] == null; i++) ;

for (minIndex = i; i < theTrees.length; i++) if (theTrees[i] != null && theTrees[i].element < theTrees[minIndex].element) minIndex = i;

return minIndex; }

/** * Remove the smallest item from the priority queue. * * @return the smallest item, or throw UnderflowException if empty. */ public int deleteMin() { if (isEmpty()) return -1; // throw new UnderflowException( );

int minIndex = findMinIndex(); int minItem = theTrees[minIndex].element;

BinNode deletedTree = theTrees[minIndex].leftChild;

// Construct H'' bqueue deletedQueue = new bqueue(); deletedQueue.expandTheTrees(minIndex);

deletedQueue.currentSize = (1 << minIndex) - 1; for (int j = minIndex - 1; j >= 0; j--) { deletedQueue.theTrees[j] = deletedTree; deletedTree = deletedTree.nextSibling; deletedQueue.theTrees[j].nextSibling = null; }

// Construct H' theTrees[minIndex] = null; currentSize -= deletedQueue.currentSize + 1;

merge(deletedQueue);

return minItem; }

/** * Test if the priority queue is logically empty. * * @return true if empty, false otherwise. */ public boolean isEmpty() { return currentSize == 0; }

/** * Make the priority queue logically empty. */ public void makeEmpty() { currentSize = 0; for (int i = 0; i < theTrees.length; i++) theTrees[i] = null; }

private static class BinNode { // Constructors BinNode(int theElement) { this(theElement, null, null); }

BinNode(int theElement, BinNode lt, BinNode nt) { element = theElement; leftChild = lt; nextSibling = nt; }

int element; // The data in the node BinNode leftChild; // Left child BinNode nextSibling; // Right child }

private static final int DEFAULT_TREES = 1;

private int currentSize; // # items in priority queue private BinNode[] theTrees; // An array of tree roots

/** * Return the capacity. */ private int capacity() { return (1 << theTrees.length) - 1; }

public static void main(String[] args) { int [] lt = new int[10000]; Scanner scan = new Scanner(System.in);

System.out.print("How many lot: "); int lot = scan.nextInt(); scan.close();

System.out.println("Randomly generating" + " no. of chips ");

for (int i = 1; i <= lot; i++) { int random = (int )(Math.random() * 128 + 1); System.out.println("Lot " + i + ": " + random); lt[i] = random; } System.out.println("Generating the chips: "); } }