[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] Skip to the content of the web site.

Leftist heap

Requirements:

In this sub-project, you will modify the class:

  1. Leftist heap: Leftist'>Leftist_heap.
  2. Leftist node: Leftist_node.

A Leftist heap is a node-based heap which is balanced. You are expected to implement or modify the member functions which are listed.

Runtime:

The run time of each member function is specified in parentheses at the end of the description.

Class Specifications:


Leftist_heap

Description

For the most part, this function simply calls the corresponding function on the root. The exceptions are size and empty (there is no requirement for each node in the heap to know the size of its descendant sub-tree), and pop is converted into a push of one sub-tree into the other. The clear function also requires a few assignments.

Friends

The class has no friends.


Leftist_heap

Description

A class which implements an leftist heap, a balanced min-heap structure.

Member Variables

All class members are already implemented.

Member Functions

Constructors

Implemented.

Copy constructor

Perform a traversal of the tree structure inserting the objects into the new tree. The structure of the tree need not be identical; for example a copy of a heap with a root of 2 may have left and right children 4 and 7, respectively, while the copy may have the children reversed. Even the null-path length of the root may be different between the original and the copy.

You may use any linked list, stack or queue data structure from either Project 1 or 2 to perform the traversal of the tree that is being copied. If you wish, you may use the Standard Template Library (STL) stack or queue classes. Please see std::queue and std::stack at cplusplus.com.

If you use your own linked list, stack or queue data structure, you must include those files with your submission. If you use the STL, you are not required to submit any other files.

Destructor

It calls clear.

Accessors

This class has five accessors which may have to be modified:

bool empty() const
Returns true if the heap is empty, false otherwise. (O(1))
int size() const
Returns the number of nodes in the heap. (O(1))
int null_path_length() const
Returns the null-path length of the root node. (O(1))
int count( const Type &obj ) const
Return the number of instances of the argument in the heap. (O(n))
Type top() const
Return the element at the top of the heap. If the tree is empty, this function throws an underflow exception. (O(1))

Mutators

This class has three mutators which may have to be modified:

void push( const Type & )
Insert the new element into the heap by creating a new leftist node and calling push on the root node using root_node as a second argument. Increment the heap size. (O(ln(n)))
Type pop()
Pop the least element in the heap and delete its node. If the tree is empty, this function throws an underflow exception. Otherwise, the left sub-tree of the root node is made the root node and the right-sub tree of the original root node is pushed into the new root node. Return the element in the popped node and decrement the heap size. (O(ln(n)))
void clear()
Call clear on the root node and reset the root node and heap size. (O(n)

Copyright ©2005-2008 by Douglas Wilhelm Harder. All rights reserved.

[an error occurred while processing this directive]