4 ms·
I don't understand this bit: > Now each of these arrays we organize as a max heap. Moreover, we arrange data such that the maximums of these heaps are in INCRE
by rntz 11y ago
I don't understand this bit:
> Now each of these arrays we organize as a max heap. Moreover, we arrange data such that the maximums of these heaps are in INCREASING order. That means the smallest element of the entire (initial) array is at the first position, then followed by the next 4 smallest organized in a max heap,
Just because the maximums of the heaps are increasing order doesn't mean that the minimum is at the front. It means the first element is smaller than the biggest element of the next four.
Consider, for example:
1 4 3 2 0
1 < 4, certainly, but 1 > 0. What am I missing?
- jcdavis 11y agoMinimum is only at the front of the entire structure, not each heap. Thats because the first element is a heap of size 1. From what I understand, the correct layout would be something like 0 4 2 3 1 Max heap of size 1 containing the smallest element, then a maxheap of size 4 containing the next 4 smallest, etc
- deciplex 11y agoI'm pretty sure there is an additional (unstated) assumption that each element of each subarray is less than all elements of subsequent subarrays. Otherwise you could just take the largest sqrt(n) elements, sort them, and then randomly assign the other elements of the collection to their heaps and it would still meet the criteria he's laid out, but the search algorithm he's proposed wouldn't work. In fact, there's an error in the search algorithm as well: > Whenever the maximum element (first element in the subarray) is smaller than the searched value, we skip over that entire heap and go to the next one. In the worst case we'll skip O(sqrt n) heaps. When the max value in a heap is less than the searched element, we found the heap and we run a linear search among O(sqrt n) elements. For the unitalicized portion above, he means to say "When the max value in a heap is greater than the searched element".