AddTree and RemoveTree

The private member functions AddTree and RemoveTree of the BinomialQueue class facilitate the implementation of the various priority queue operations. These functions are defined in Program . The AddTree function takes a reference to a BinomialTree and appends a pointer to that tree to list. AddTree also adjusts the count in order to keep track of the number of items in the priority queue. It is assumed that the order of the tree which is added is larger than all the others in the list and, therefore, that it belongs at the end of the list. The running time of AddTree is clearly O(1).

  
Program: BinomialQueue Class AddTree and RemoveTree Member Function Definitions

The RemoveTree function takes a reference to a binomial tree and removes it from the list. It is assumed that the specified tree is actually in the list. RemoveTree also adjust the count as required. The running time of RemoveTree depends on the position of the tree in the list. A binomial queue which contains exactly n items altogether has at most binomial trees. Therefore, the running time of RemoveTree is in the worst case.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.