Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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 gif. 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).

   program27519
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 tex2html_wrap_inline66948 binomial trees. Therefore, the running time of RemoveTree is tex2html_wrap_inline59891 in the worst case.


next up previous contents index

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