C++ Programming Code Examples
C++ > Data Structures and Algorithm Analysis in C++ Code Examples
Implementation for pairing heap
/* Implementation for pairing heap */
#include "PairingHeap.h"
#include "dsexceptions.h"
/**
* Construct the pairing heap.
*/
template <class Comparable>
PairingHeap<Comparable>::PairingHeap( )
{
root = NULL;
}
/**
* Copy constructor
*/
template <class Comparable>
PairingHeap<Comparable>::PairingHeap( const PairingHeap<Comparable> & rhs )
{
root = NULL;
*this = rhs;
}
/**
* Destroy the leftist heap.
*/
template <class Comparable>
PairingHeap<Comparable>::~PairingHeap( )
{
makeEmpty( );
}
/**
* Insert item x into the priority queue, maintaining heap order.
* Return a pointer to the node containing the new item.
*/
template <class Comparable>
PairNode<Comparable> *
PairingHeap<Comparable>::insert( const Comparable & x )
{
PairNode<Comparable> *newNode = new PairNode<Comparable>( x );
if( root == NULL )
root = newNode;
else
compareAndLink( root, newNode );
return newNode;
}
/**
* Find the smallest item in the priority queue.
* Return the smallest item, or throw Underflow if empty.
*/
template <class Comparable>
const Comparable & PairingHeap<Comparable>::findMin( ) const
{
if( isEmpty( ) )
throw Underflow( );
return root->element;
}
/**
* Remove the smallest item from the priority queue.
* Throws Underflow if empty.
*/
template <class Comparable>
void PairingHeap<Comparable>::deleteMin( )
{
if( isEmpty( ) )
throw Underflow( );
PairNode<Comparable> *oldRoot = root;
if( root->leftChild == NULL )
root = NULL;
else
root = combineSiblings( root->leftChild );
delete oldRoot;
}
/**
* Remove the smallest item from the priority queue.
* Pass back the smallest item, or throw Underflow if empty.
*/
template <class Comparable>
void PairingHeap<Comparable>::deleteMin( Comparable & minItem )
{
minItem = findMin( );
deleteMin( );
}
/**
* Test if the priority queue is logically empty.
* Returns true if empty, false otherwise.
*/
template <class Comparable>
bool PairingHeap<Comparable>::isEmpty( ) const
{
return root == NULL;
}
/**
* Test if the priority queue is logically full.
* Returns false in this implementation.
*/
template <class Comparable>
bool PairingHeap<Comparable>::isFull( ) const
{
return false;
}
/**
* Make the priority queue logically empty.
*/
template <class Comparable>
void PairingHeap<Comparable>::makeEmpty( )
{
reclaimMemory( root );
root = NULL;
}
/**
* Deep copy.
*/
template <class Comparable>
const PairingHeap<Comparable> &
PairingHeap<Comparable>::operator=( const PairingHeap<Comparable> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
/**
* Internal method to make the tree empty.
* WARNING: This is prone to running out of stack space.
*/
template <class Comparable>
void PairingHeap<Comparable>::reclaimMemory( PairNode<Comparable> * t ) const
{
if( t != NULL )
{
reclaimMemory( t->leftChild );
reclaimMemory( t->nextSibling );
delete t;
}
}
/**
* Change the value of the item stored in the pairing heap.
* Does nothing if newVal is larger than currently stored value.
* p points to a node returned by insert.
* newVal is the new value, which must be smaller
* than the currently stored value.
*/
template <class Comparable>
void PairingHeap<Comparable>::decreaseKey( PairNode<Comparable> *p,
const Comparable & newVal )
{
if( p->element < newVal )
return; // newVal cannot be bigger
p->element = newVal;
if( p != root )
{
if( p->nextSibling != NULL )
p->nextSibling->prev = p->prev;
if( p->prev->leftChild == p )
p->prev->leftChild = p->nextSibling;
else
p->prev->nextSibling = p->nextSibling;
p->nextSibling = NULL;
compareAndLink( root, p );
}
}
/**
* Internal method that is the basic operation to maintain order.
* Links first and second together to satisfy heap order.
* first is root of tree 1, which may not be NULL.
* first->nextSibling MUST be NULL on entry.
* second is root of tree 2, which may be NULL.
* first becomes the result of the tree merge.
*/
template <class Comparable>
void PairingHeap<Comparable>::
compareAndLink( PairNode<Comparable> * & first,
PairNode<Comparable> *second ) const
{
if( second == NULL )
return;
if( second->element < first->element )
{
// Attach first as leftmost child of second
second->prev = first->prev;
first->prev = second;
first->nextSibling = second->leftChild;
if( first->nextSibling != NULL )
first->nextSibling->prev = first;
second->leftChild = first;
first = second;
}
else
{
// Attach second as leftmost child of first
second->prev = first;
first->nextSibling = second->nextSibling;
if( first->nextSibling != NULL )
first->nextSibling->prev = first;
second->nextSibling = first->leftChild;
if( second->nextSibling != NULL )
second->nextSibling->prev = second;
first->leftChild = second;
}
}
/**
* Internal method that implements two-pass merging.
* firstSibling the root of the conglomerate;
* assumed not NULL.
*/
template <class Comparable>
PairNode<Comparable> *
PairingHeap<Comparable>::
combineSiblings( PairNode<Comparable> *firstSibling ) const
{
if( firstSibling->nextSibling == NULL )
return firstSibling;
// Allocate the array
static vector<PairNode<Comparable> *> treeArray( 5 );
// Store the subtrees in an array
int numSiblings = 0;
for( ; firstSibling != NULL; numSiblings++ )
{
if( numSiblings == treeArray.size( ) )
treeArray.resize( numSiblings * 2 );
treeArray[ numSiblings ] = firstSibling;
firstSibling->prev->nextSibling = NULL; // break links
firstSibling = firstSibling->nextSibling;
}
if( numSiblings == treeArray.size( ) )
treeArray.resize( numSiblings + 1 );
treeArray[ numSiblings ] = NULL;
// Combine subtrees two at a time, going left to right
int i = 0;
for( ; i + 1 < numSiblings; i += 2 )
compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
int j = i - 2;
// j has the result of last compareAndLink.
// If an odd number of trees, get the last one.
if( j == numSiblings - 3 )
compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
// Now go right to left, merging last tree with
// next to last. The result becomes the new last.
for( ; j >= 2; j -= 2 )
compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
return treeArray[ 0 ];
}
/**
* Internal method to clone subtree.
* WARNING: This is prone to running out of stack space.
*/
template <class Comparable>
PairNode<Comparable> *
PairingHeap<Comparable>::clone( PairNode<Comparable> * t ) const
{
if( t == NULL )
return NULL;
else
{
PairNode<Comparable> *p = new PairNode<Comparable>( t->element );
if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
p->leftChild->prev = p;
if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
p->nextSibling->prev = p;
return p;
}
}
Change size. Resizes the container so that it contains n elements. The vector is a very useful class of C++ for creating the dynamic array. The size of the vector can be changed at any time to solve any programming problem. Many built-in functions exist in C++ for doing the different types of tasks in a vector container. The resize() function is one of them. It is used to change the size of the vector. The vector size can be increased or decreased by using this function. This function does not return any value. If a reallocation happens, the storage is allocated using the container's allocator, which may throw exceptions on failure (for the default allocator, bad_alloc is thrown if the allocation request does not succeed).
A destructor is a special member function that works just opposite to constructor, unlike constructors that are used for initializing an object, destructors destroy (or delete) the object. Destructors in C++ are members functions in a class that delete an object. They are called when the class object goes out of scope such as when the function ends, the program ends, a delete variable is called etc. Destructors are different from normal member functions as they don't take any argument and don't return anything. Also, destructors have the same name as their class and their name is preceded by a tilde(~).
Return the smallest. Returns the smallest of a and b. If both are equivalent, a is returned. min() function is a library function of algorithm header, it is used to find the smallest value from given two values, it accepts two values and returns the smallest value and if both the values are the same it returns the first value. The versions for initializer lists (3) return the smallest of all the elements in the list. Returning the first of them if these are more than one. The function uses operator< (or comp, if provided) to compare the values.
#include is a way of including a standard or user-defined file in the program and is mostly written at the beginning of any C/C++ program. This directive is read by the preprocessor and orders it to insert the content of a user-defined or system header file into the following program. These files are mainly imported from an outside source into the current program. The process of importing such files that might be system-defined or user-defined is known as File Inclusion. This type of preprocessor directive tells the compiler to include a file in the source code program.
An array is defined as the collection of similar type of data items stored at contiguous memory locations. Arrays are the derived data type in C++ programming language which can store the primitive type of data such as int, char, double, float, etc. It also has the capability to store the collection of derived data types, such as pointers, structure, etc. The array is the simplest data structure where each data element can be randomly accessed by using its index number. C++ array is beneficial if you have to store similar elements. For example, if we want to store the marks of a student in 6 subjects, then we don't need to define different variables for the marks in the different subject. Instead of that, we can define an array which can store the marks in each subject at the contiguous memory locations.
Deallocate storage space. Default deallocation functions (single-object form). A delete operator is used to deallocate memory space that is dynamically created using the new operator, calloc and malloc() function, etc., at the run time of a program in C++ language. In other words, a delete operator is used to release array and non-array (pointer) objects from the heap, which the new operator dynamically allocates to put variables on heap memory. We can use either the delete operator or delete [ ] operator in our program to delete the deallocated space. A delete operator has a void return type, and hence, it does not return a value.
Access element. Returns a reference to the element at position n in the vector container. A similar member function, vector::at, has the same behavior as this operator function, except that vector::at is bound-checked and signals if the requested position is out of range by throwing an out_of_range exception. Portable programs should never call this function with an argument n that is out of range, since this causes undefined behavior. Function returns the element at the specified position in the vector.
Static is a keyword in C++ used to give special characteristics to an element. Static elements are allocated storage only once in a program lifetime in static storage area. And they have a scope till the program lifetime. In C++, static is a keyword or modifier that belongs to the type not instance. So instance is not required to access the static members. In C++, static can be field, method, constructor, class, properties, operator and event. Advantage of C++ static keyword: Memory efficient. Now we don't need to create instance for accessing the static members, so it saves memory. Moreover, it belongs to the type, so it will not get memory each time when instance is created.
Every object in C++ has access to its own address through an important pointer called this pointer. The this pointer is an implicit parameter to all member functions. Therefore, inside a member function, this may be used to refer to the invoking object. Friend functions do not have a this pointer, because friends are not members of a class. Only member functions have a this pointer. In C++ programming, this is a keyword that refers to the current instance of the class. There can be 3 main usage of this keyword in C++: • It can be used to pass current object as a parameter to another method. • It can be used to refer current class instance variable. • It can be used to declare indexers. To understand 'this' pointer, it is important to know how objects look at functions and data members of a class.
Return size. Returns the number of elements in the vector. This is the number of actual objects held in the vector, which is not necessarily equal to its storage capacity. vector::size() is a library function of "vector" header, it is used to get the size of a vector, it returns the total number of elements in the vector. The dynamic array can be created by using a vector in C++. One or more elements can be inserted into or removed from the vector at the run time that increases or decreases the size of the vector. The size or length of the vector can be counted using any loop or the built-in function named size(). This function does not accept any parameter.
In C++, vectors are used to store elements of similar data types. However, unlike arrays, the size of a vector can grow dynamically. That is, we can change the size of the vector during the execution of a program as per our requirements. Vectors are part of the C++ Standard Template Library. To use vectors, we need to include the vector header file in our program. The vector class provides various methods to perform different operations on vectors. Add Elements to a Vector: To add a single element into a vector, we use the push_back() function. It inserts an element into the end of the vector. Access Elements of a Vector: In C++, we use the index number to access the vector elements. Here, we use the at() function to access the element from the specified index.
In computer programming, we use the if statement to run a block code only when a certain condition is met. An if statement can be followed by an optional else statement, which executes when the boolean expression is false. There are three forms of if...else statements in C++: • if statement, • if...else statement, • if...else if...else statement, The if statement evaluates the condition inside the parentheses ( ). If the condition evaluates to true, the code inside the body of if is executed. If the condition evaluates to false, the code inside the body of if is skipped.
The if...else statement executes two different codes depending upon whether the test expression is true or false. Sometimes, a choice has to be made from more than 2 possibilities. The if...else ladder allows you to check between multiple test expressions and execute different statements. In C/C++ if-else-if ladder helps user decide from among multiple options. The C/C++ if statements are executed from the top down. As soon as one of the conditions controlling the if is true, the statement associated with that if is executed, and the rest of the C else-if ladder is bypassed. If none of the conditions is true, then the final else statement will be executed.
As the name already suggests, these operators help in assigning values to variables. These operators help us in allocating a particular value to the operands. The main simple assignment operator is '='. We have to be sure that both the left and right sides of the operator must have the same data type. We have different levels of operators. Assignment operators are used to assign the value, variable and function to another variable. Assignment operators in C are some of the C Programming Operator, which are useful to assign the values to the declared variables. Let's discuss the various types of the assignment operators such as =, +=, -=, /=, *= and %=. The following table lists the assignment operators supported by the C language:
The pointer in C++ language is a variable, it is also known as locator or indicator that points to an address of a value. In C++, a pointer refers to a variable that holds the address of another variable. Like regular variables, pointers have a data type. For example, a pointer of type integer can hold the address of a variable of type integer. A pointer of character type can hold the address of a variable of character type. You should see a pointer as a symbolic representation of a memory address. With pointers, programs can simulate call-by-reference. They can also create and manipulate dynamic data structures. In C++, a pointer variable refers to a variable pointing to a specific address in a memory pointed by another variable.
In C++, classes and structs are blueprints that are used to create the instance of a class. Structs are used for lightweight objects such as Rectangle, color, Point, etc. Unlike class, structs in C++ are value type than reference type. It is useful if you have data that is not intended to be modified after creation of struct. C++ Structure is a collection of different data types. It is similar to the class that holds different types of data. A structure is declared by preceding the struct keyword followed by the identifier(structure name). Inside the curly braces, we can declare the member variables of different types.
Templates are powerful features of C++ which allows us to write generic programs. Similar to function templates, we can use class templates to create a single class to work with different data types. Class templates come in handy as they can make our code shorter and more manageable. A class template starts with the keyword template followed by template parameter(s) inside <> which is followed by the class declaration. T is the template argument which is a placeholder for the data type used, and class is a keyword. Inside the class body, a member variable var and a member function functionName() are both of type T.
Allocate storage space. Default allocation functions (single-object form). A new operator is used to create the object while a delete operator is used to delete the object. When the object is created by using the new operator, then the object will exist until we explicitly use the delete operator to delete the object. Therefore, we can say that the lifetime of the object is not related to the block structure of the program.
A C++ template is a powerful feature added to C++. It allows you to define the generic classes and generic functions and thus provides support for generic programming. Generic programming is a technique where generic types are used as parameters in algorithms so that they can work for a variety of data types. We can define a template for a function. For example, if we have an add() function, we can create versions of the add function for adding the int, float or double type values. Where Ttype: It is a placeholder name for a data type used by the function. It is used within the function definition. It is only a placeholder that the compiler will automatically replace this placeholder with the actual data type. class: A class keyword is used to specify a generic type in a template declaration.
In computer programming, loops are used to repeat a block of code. For example, when you are displaying number from 1 to 100 you may want set the value of a variable to 1 and display it 100 times, increasing its value by 1 on each loop iteration. When you know exactly how many times you want to loop through a block of code, use the for loop instead of a while loop. A for loop is a repetition control structure that allows you to efficiently write a loop that needs to execute a specific number of times.
In the C++ Programming, The static keyword allows a variable to maintain its value among different function calls. If the value of a static variable changes when the variable has been
Perform addition, subtraction, multiplication and division of any two numbers in 'C++', you have to enter the 'two number' and enter the operator to perform the particular operation
In this example, if...else statement is used to check whether a number entered by the user is "even or odd". Integers which are perfectly "divisible by 2" are called even numbers. And
Program demonstrates implementation of max-flow_min-cut_theorem. So returns true if there is a 'path from source' 's' to sink 't' in residual graph. Also fills parent[] to store the
