Part 1 Command Modifications

The following commands from Part 1 will not be tested in Part 2, but are expected to appear in Part 3 and Part 4 with a high probability. So, we are including the modifications needed to update them for later use, in case you choose to develop them early for other reasons.

TRANSFER_ITEM(name1, name2)

name1:case-sensitive string representation of a friendly base name2:case-sensitive string representation of a friendly base This transfers one item from name1 to name2. So, the min element of the Fibonacci heap (of name1) will be removed and then inserted to the inventory of the second argument. Note that there is NO dictionary type; this is because you can ONLY transfer between friendly bases. The children of the min element will be brought up one level in the exact position their parent was located. There will be a consolidation stage perfomed. Also, you will need to update the min element with the next smallest element in the root list. An error message will be printed if either of the bases do not exist or if either base in not mapped. Also, if the first base has an empty inventory, print the final message. Should be log(n) amortized runtime.

Output summary:
<output>:= <success>|<error>
<success>:=item transfer complete
<error>:=<SiteDoesNotExist>|<SiteNotMapped>|<EmptyInventory>

TRANSFER_ALL(name1, name2)

name1:case-sensitive string representation of a friendly base name2:case-sensitive string representation of a friendly base Put the heap of name1 into the heap of name2. See examples of Union. The first argument's heap should be empty if this operation is successful. You will not consolidate the structure to have at most one binomial heap of a given degree. This should be done in constant time. Note that there is NO dictionary type; this is because you can ONLY transfer between friendly bases.

Output summary:
<output>:= <success>|<error>
<success>:=everything transfered
<error>:=<SiteDoesNotExist>|<SiteNotMapped>|<EmptyInventory>

TRANSFER_ALL_WITH_CONSOLIDATE(name1, name2)

name1:case-sensitive string representation of a friendly base name2:case-sensitive string representation of a friendly base Put the heap of name1 into the heap of name2. See examples of Merge. The first argument's heap should be empty if this operation is successful. You will consolidate the structure to have at most one binomial heap of a given degree. Note that there is NO dictionary type; this is because you can ONLY transfer between friendly bases.

Output summary:
<output>:= <success>|<error>
<success>:=everything transfered
<error>:=<SiteDoesNotExist>|<SiteNotMapped>|<EmptyInventory>

CONSOLIDATE(name1)

name1:case-sensitive string represention of a friendly base Explicit call to consolidate the heaps of the mapped base with specified name. You must maintain the heap property for each binomial heap of a given degree. The first error will be displayed if the base is not in the data dictionary. If the base is not on the map currently, print the second error message. If the heap is empty, you will print the final error message. You will consolidate the structure to have at most one binomial heap of a given degree. Note that there is NO dictionary type; this is because you can ONLY transfer between friendly bases.

Output summary:
<output>:= <success>|<error>
<success>:=consolidated heap
<error>:=<SiteDoesNotExist>|<SiteNotMapped>|<EmptyInventory>

PRINT_HEAP(name)

name:case-sensitive string representation of a friendly base You will print each key in the heap in the following manner: enclosed in parentheses, print each node's value in the root list. If that node has any children, print them immeadiately next to that node in parentheses. This process will be applied recursively. Therefore, on one line you will be displaying the entire heap. Color is used in the example to make the nesting more apparent. We will be testing each individual binomial heap for the heap property. Also, we will verify that there are at most one heap of each degree. Note: this display is followed by a new line (\n).

The heap is to be printed in the following manner: a) output left parenthesis b) beginning with the min value in the f-heap, for each binomial heap in the forest, output the root value output the roots of its child subtrees enclosed in parentheses repeat recursively until all subtrees have been printed c) output right parenthesis) output a new line (\n)

This is a standard linear respresentation of a forest of general trees that can be used to serialize such structures. It will allow us to verify that your fibonacci heap satisfies the constraints for such structures, regardless of the specific ordering of values in the f-heap.

SAMPLE FIBONACCI HEAP

               7-----------52--------------18
               |                            |
               |                            |
   24-----17---30                           |    
    |      |                           41---39
    |      |                           |
26--46    23                           | 
 |                                     |
 |                                     44
 |                                    
 35

( 7 ( 24 ( 26 ( 35 ) 46 ) 17 ( 23 ) 30) 52 18 ( 41 ( 44 ) 39 ) )

You must have at least one value within each set of parentheses. This will be called on the MIN element. This means printing will begin with the min element.

Output summary:
<output>:= <success>|<error>
<success>:=<PrintRow>
<PrintRow>:=( PrintEachNode  )
<PrintEachNode>:=<NodeDisplay> <PrintEachNode>| <NodeDisplay>
<NodeDisplay>:= <value of node> <PrintRow>| <value of node> 
<error>:=<HeapEmpty>

Web Accessibility