C++ please just implement the remove function for the heap code below. Include c
ID: 3819239 • Letter: C
Question
C++ please just implement the remove function for the heap code below. Include comments where needed to explain. Thank you!
---------------------------------------------------------------------------------------------------------
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType,KeyType,Comparator>::Heap ( int maxNumber = DEFAULT_MAX_HEAP_SIZE )
{
maxSize = maxNumber;
size = 0;
dataItems = new DataType[maxSize];
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType,KeyType,Comparator>::Heap ( const Heap& other )
{
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType,KeyType,Comparator>& Heap<DataType,KeyType,Comparator>::operator= ( const Heap& other )
{
}
template < typename DataType, typename KeyType, typename Comparator >
Heap<DataType,KeyType,Comparator>::~Heap ()
{
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>::insert ( const DataType &newDataItem )
throw ( logic_error )
{
}
template < typename DataType, typename KeyType, typename Comparator >
DataType Heap<DataType,KeyType,Comparator>::remove () throw ( logic_error )
{
}
template < typename DataType, typename KeyType, typename Comparator >
void Heap<DataType,KeyType,Comparator>::clear ()
{
size = 0;
}
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType,KeyType,Comparator>::isEmpty () const
{
}
//size is maxSize, is full
template < typename DataType, typename KeyType, typename Comparator >
bool Heap<DataType,KeyType,Comparator>::isFull () const
{
}
Explanation / Answer
Please rate me, the answer is helpful to you. thank you
remove() Function: Removes the highest priority data item (the root) from this Heap and returns it. Replaces the root data item with the bottom right most data item and moves this data item downward until the properties that define a heap is restored.
template<typename DataType, typename KeyType, typename Comparator>
DataType Heap<DataType, KeyType, Comparator>::remove() throw (logic_error)
{
if(isEmpty() == true)
{
throw logic_error("Empty List");//throw This Heap is empty.
}
size--;
//Set the return dataItem
DataType returnDataItem = dataItems[0];
dataItems[0] = dataItems[size];
//Iterate through the Heap
int pos = 0;
while(pos < size)
{
Comparator compare;//for campare two priorities
if((pos * 2) + 2 <= size)
{
//No switch is requierd if two priorities same
if(compare(dataItems[pos].getPriority(),dataItems[(pos * 2) + 1].getPriority()) &&
compare(dataItems[pos].getPriority(),dataItems[(pos * 2) + 2].getPriority()))
{
return returnDataItem;
}
//Swap items if greater priority than other
else if(compare(dataItems[(pos * 2) + 2].getPriority(), dataItems[(pos * 2) + 1].getPriority()))
{
DataType data = dataItems[pos];
dataItems[pos] = dataItems[(pos * 2) + 2];
dataItems[(pos * 2) + 2] = data;
pos = (pos * 2) + 2;
}
//Swap items if less priority than
else
{
DataType data = dataItems[pos];
dataItems[pos] = dataItems[pos + 1];
dataItems[(pos * 2) + 1] = data;
pos = (pos * 2) + 1;
}
}
else if( (pos * 2) + 1 <= size)//if (pos * 2) + 1 is lessthen or equal to size
{
// then Swap items if greater priority than
if(compare(dataItems[(pos * 2) + 1].getPriority(),dataItems[pos].getPriority()))
{
DataType data= dataItems[pos];
dataItems[pos] = dataItems[(pos * 2) + 1];
dataItems[(pos * 2) + 1] = data;
pos = (pos * 2) + 1;
}
else
{
return returnDataItem;
}
}
else
{
return returnDataItem;
}
}
return returnDataItem;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.