2 3 *Standard heapsort template void heapsort ( vector & a ) 5 6 for ( int i a.s

Question

2 3 *Standard heapsort template void heapsort ( vector & a ) 5 6 for ( int i a.size( ) / 2-1; i >= 0; --i ) /* buildHea p */ percDown a, i, a.size() ):; 8 9 10 for int j-a.size( 1; j>0; j std:: swap a 0], a j]; percDown a, 0, j ); /*deleteMax * 12 13 15 16 17 18 19 20 21 *Internal method for heapsort. *i is the index of an item in the heap. *Returns the index of theleft child. inline int leftChild( int i) 23 24 25 26 /** 27 28 29 30 31 32 return 2*i+ 1; *Internal method for heapsort that is used in deleteMax and bui 1 dHeap *i is the position from which to percolate down *n is the 1ogical size of the binary heap templ ate

Explanation / Answer

"The complexity should be O(nLog n)... for each item we "heapify", it has the potential to have to filter down once for each level for the heap so far (which is log n levels)."
Not quite. Your logic does not produce a tight bound -- it over estimates the complexity of each heapify. If built from the bottom up, insertion (heapify) can be much less than O(log(n)). The process is as follows:

( Step 1 ) The first n/2 elements go on the bottom row of the heap. h=0, so heapify is not needed.

( Step 2 ) The next n/22 elements go on the row 1 up from the bottom. h=1, heapify filters 1 level down.

( Step i ) The next n/2i elements go in row i up from the bottom. h=i, heapify filters i levels down.

( Step log(n) ) The last n/2log2(n) = 1 element goes in row log(n) up from the bottom. h=log(n), heapify filters log(n) levels down.

NOTICE: that after step one, 1/2 of the elements (n/2) are already in the heap, and we didn't even need to call heapify once. Also, notice that only a single element, the root, actually incurs the full log(n) complexity.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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