MinHeap< T > Class Template Reference

This class models a structure called a MinHeap in which value in the root node is minimum. More...

#include <MinHeap.h>

Public Member Functions
	MinHeap ()
	~MinHeap ()
bool	isEmpty ()
int	getSize ()
T	min ()
void	insert (const T &)
	Adds value of type T to the MinHeap. More...
T	remove ()
	Removes and returns the minimum value. More...
void	display ()
	Prints the values of the MinHeap. More...

Private Member Functions
int	parent (int)
	Vector of items of MinHeap. More...
int	leftChild (int)
int	rightChild (int)
template<typename U = T>
std::enable_if< std::is_pointer< U >::value, int >::type	smallerChild (int index)
template<typename U = T>
std::enable_if<!std::is_pointer< U >::value, int >::type	smallerChild (int index)
bool	hasLeftChild (int)
bool	hasRightChild (int)
template<typename U = T>
std::enable_if< std::is_pointer< U >::value, bool >::type	isValidParent (int index)
template<typename U = T>
std::enable_if<!std::is_pointer< U >::value, bool >::type	isValidParent (int index)
template<typename U = T>
std::enable_if< std::is_pointer< U >::value, void >::type	bubbleUp ()
	Bubbles up the value to meet the MinHeap property. More...
template<typename U = T>
std::enable_if<!std::is_pointer< U >::value, void >::type	bubbleUp ()
void	bubbleDown ()
	Bubbles down the value to meet the MinHeap property. More...
void	swap (int, int)
	swap two values in the items vector More...

Private Attributes
std::vector< T >	items

Detailed Description

template<class T>
class MinHeap< T >

This class models a structure called a MinHeap in which value in the root node is minimum.

It is a complete binary tree in which the value contained in each node is less than (or equal to) the value in that node's children.

Definition at line 18 of file MinHeap.h.

Constructor & Destructor Documentation

MinHeap()

template<class T >

MinHeap< T >::MinHeap

Definition at line 98 of file MinHeap.h.

~MinHeap()

template<class T >

MinHeap< T >::~MinHeap

Definition at line 103 of file MinHeap.h.

Member Function Documentation

bubbleDown()

template<class T >

void MinHeap< T >::bubbleDown

private

Bubbles down the value to meet the MinHeap property.

See also

remove()

Definition at line 188 of file MinHeap.h.

bubbleUp() [1/2]

template<typename T >

template<typename U >

std::enable_if<!std::is_pointer< U >::value, void >::type MinHeap< T >::bubbleUp

private

Bubbles up the value to meet the MinHeap property.

See also

insert()

Definition at line 155 of file MinHeap.h.

bubbleUp() [2/2]

template<class T >

template<typename U = T>

std::enable_if<!std::is_pointer<U>::value, void >::type MinHeap< T >::bubbleUp ( )

private

display()

template<class T >

void MinHeap< T >::display

Prints the values of the MinHeap.

Definition at line 250 of file MinHeap.h.

getSize()

template<class T >

int MinHeap< T >::getSize

Returns

the number of values in the MinHeap.

Definition at line 113 of file MinHeap.h.

hasLeftChild()

template<class T >

bool MinHeap< T >::hasLeftChild ( int  index )

private

Returns

true if parameter index has left child

Definition at line 198 of file MinHeap.h.

hasRightChild()

template<class T >

bool MinHeap< T >::hasRightChild ( int  index )

private

Returns

true if parameter index has right child

Definition at line 203 of file MinHeap.h.

insert()

template<class T >

void MinHeap< T >::insert

(

const T &

value

)

Adds value of type T to the MinHeap.

Definition at line 149 of file MinHeap.h.

isEmpty()

template<class T >

bool MinHeap< T >::isEmpty

Returns

true if the MinHeap contains no elements.

Definition at line 108 of file MinHeap.h.

isValidParent() [1/2]

template<typename T >

template<typename U >

std::enable_if<!std::is_pointer< U >::value, bool >::type MinHeap< T >::isValidParent ( int  index )

private

Definition at line 208 of file MinHeap.h.

isValidParent() [2/2]

template<class T >

template<typename U = T>

std::enable_if<!std::is_pointer<U>::value, bool >::type MinHeap< T >::isValidParent ( int  index )

private

leftChild()

template<class T >

int MinHeap< T >::leftChild ( int  index )

private

Returns

left child index of a parameter index

Definition at line 123 of file MinHeap.h.

min()

template<class T >

T MinHeap< T >::min

Returns

the minimum value in the MinHeap.

Definition at line 140 of file MinHeap.h.

parent()

template<class T >

int MinHeap< T >::parent ( int  index )

private

Vector of items of MinHeap.

Returns

parent index of a parameter index

Definition at line 118 of file MinHeap.h.

remove()

template<class T >

T MinHeap< T >::remove

Removes and returns the minimum value.

Returns

root node

Definition at line 173 of file MinHeap.h.

rightChild()

template<class T >

int MinHeap< T >::rightChild ( int  index )

private

Returns

right child index of a parameter index

Definition at line 128 of file MinHeap.h.

smallerChild() [1/2]

template<typename T >

template<typename U >

std::enable_if<!std::is_pointer< U >::value, int >::type MinHeap< T >::smallerChild ( int  index )

private

Returns

smaller child of parameter index

Definition at line 228 of file MinHeap.h.

smallerChild() [2/2]

template<class T >

template<typename U = T>

std::enable_if<!std::is_pointer<U>::value, int >::type MinHeap< T >::smallerChild ( int  index )

private

swap()

template<class T >

void MinHeap< T >::swap ( int  first, int  second  )

private

swap two values in the items vector

Parameters

index

of the two values to be swapped

Definition at line 133 of file MinHeap.h.

Member Data Documentation

items

template<class T >

std::vector<T> MinHeap< T >::items

private

Definition at line 20 of file MinHeap.h.