Example of TreeSort template <typename c> void TreeSort(vector<C>& data, int& co

Question

Example of TreeSort

template <typename c>
void TreeSort(vector<C>& data, int& comps)
{

CLUMSY_COUNT = 0;

BinarySearchTree<C> bst;

// enter all N many many data items into the bst;
// loops iterates N times; each iteration has cost 0(log N);
// thus: cost of this loop is 0(N log N);

for (int i = 0; i < data.size(); i++)
{
bst.insert(data[i]); // average cost of insertion 0(loq N)
}

// iterate through the bst, access each data item in turn and
// copy it back into the ith field in the vector;
// cost: 0(N)

int i = O;
typename BinarySearchTree<C>z:iterator itr = bst.begin();
for (; itr != bst.end(); ++itr)
{
data[i] = *itr;
i++;
} // total cost: om log N) + om) = om log N)
comps = CLUMSY_COUNT;
}

Task 1: Complete the implementation of the HeapSort function, following the example of TreeSort. The binary heap data structure does not have an iterator, but based on your knowledge of the BinaryHeap interface, you should find a suitable alternative for what needs to happen.

--------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------------------------------------------------

Explanation / Answer

Just call ++ operator of BST class because each invocation of it will give you the next big element. I see that this function is implementing inorder traversal and inorder traversal over BST is nothing but a HeapSort!

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.