Assume the following list: 30, 45, 1, 26, 90, 5, 85, 35, 20, 41, 38, 72, 11, 33, 49 Using the function buildHeap as given in this chapter, convert the list into a heap. Show the resulting list after three passes of heapsort. (Use the heapify procedure as given in this chapter.) One pass:________________________________________________ Two passes:_______________________________________________ Three passes:______________________________________________ //---------buildHeap function-------------------- template void arrayListType::buildHeap() { for (int index = length / 2 - 1; index >= 0; index--) heapify(index, length - 1); }//end buildheap //-----------heapify function------------------ template void arrayListType::heapify(int low, int high) { int largeIndex; elemType temp = list[low]; //copy the root node of the subtree largeIndex = 2 * low + 1; //index of the left child while (largeIndex <= high) { if (largeIndex < high) if (list[largeIndex] < list[largeIndex + 1]) largeIndex = largeIndex + 1; //index of the largest //child if (temp > list[largeIndex]) //subtree is already in a heap break; else { list[low] = list[largeIndex]; //move the larger child //to the root low = largeIndex; //go to the subtree to restore the heap largeIndex = 2 * low + 1; } }//end while list[low] = temp; //insert temp into the tree, that is, list } //end heapify
Assume the following list:
30, 45, 1, 26, 90, 5, 85, 35, 20, 41, 38, 72, 11, 33, 49
- Using the function buildHeap as given in this chapter, convert the list into a heap.
- Show the resulting list after three passes of heapsort. (Use the heapify procedure as given in this chapter.)
One pass:________________________________________________
Two passes:_______________________________________________
Three passes:______________________________________________
//---------buildHeap function--------------------
template <class elemType>
void arrayListType<elemType>::buildHeap()
{
for (int index = length / 2 - 1; index >= 0; index--)
heapify(index, length - 1);
}//end buildheap
//-----------heapify function------------------
template<class elemType>
void arrayListType<elemType>::heapify(int low, int high)
{
int largeIndex;
elemType temp = list[low]; //copy the root node of the subtree
largeIndex = 2 * low + 1; //index of the left child
while (largeIndex <= high)
{
if (largeIndex < high)
if (list[largeIndex] < list[largeIndex + 1])
largeIndex = largeIndex + 1; //index of the largest
//child
if (temp > list[largeIndex]) //subtree is already in a heap
break;
else
{
list[low] = list[largeIndex]; //move the larger child
//to the root
low = largeIndex; //go to the subtree to restore the heap
largeIndex = 2 * low + 1;
}
}//end while
list[low] = temp; //insert temp into the tree, that is, list
} //end heapify
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 4 images
