Question

This is in java and it is building a Binomial Queues.

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

Answer 1

A data structure is called distribution-sensitive if the asymptotic time bound

taken by the structure to perform an operation varies according to the distribu-

tion of the input sequence. Though having upper bounds on the running time

of different operations over all possible sequences, some structures may perform

better for some sequences than others. This is analogous to a sorting algorithm

running in O(n log n) for any sequence of length n, while performing better and

running in O(n) if the input is already sorted or inversely sorted.

In order to characterize such structures, several properties are introduced

describing the behavior of these structures. These properties can be viewed as

characterizations of distribution-sensitive behavior that give insights into the

possibilities and limitations of these data structures. Relationships among such

properties are introduced in [15], thus establishing a hierarchy of properties.

Following finger trees [13], splay trees [20] is the classical example of a

distribution-sensitive structure. Most of the known distribution-sensitive prop-

erties were introduced either as theorems or conjectures characterizing the per-

formance of splay trees. Examples are: The static optimality theorem, the static

finger theorem, the working-set theorem (all in [20]), the sequential access the-

orem [11, 21, 22], the dequeue theorem [21], and the dynamic finger theorem [4].

Each of these theorems describes a natural class of sequences of operations, and

shows that the amortized cost of performing any of these sequences on an n-

node splay tree is o(log n) per operation. With a special interest with respect

to our structure, we present the working-set property for search trees: The time

spent to search item x in a search tree is O(log w

x

), where w

x

is the number of

distinct items that have been accessed since x’s last access. Informally, in a data

structure with the working-set property accesses to items recently accessed are

faster than accesses to items that have not been accessed in a while.