> Building the structure. Why is this O(n)? If you have already segregated the array into segments for the separate heaps, heapifying them would be O(n). How can the segmentation be done in O(n)?
Using 1 + 3 + 5 ... = n^2, wouldn't the largest segment hold roughly sqrt(n) elements. So O(sort(n)) heapify for sqrt(n) heaps, or O(sqrt(n) * sqrt(n)) = O(n).
Using 1 + 3 + 5 ... = n^2, wouldn't the largest segment hold roughly sqrt(n) elements. So O(sort(n)) heapify for sqrt(n) heaps, or O(sqrt(n) * sqrt(n)) = O(n).