Sloppy heap sort
Has anyone heard of this heap repair technique: SloppyHeapSort? It uses the "Sloppy" sift-down approach. Basically, what needs to be repaired is an element, moves it to the bottom of the heap (not comparing it to its children), replacing it with its larger child until it hits the bottom. Then, sift-up is called until it reaches its correct location. This makes just over lg n comparisons (on a heap of size n).
However, this cannot be used to build the heap, only to repair the heap. Why is this? I don't understand why this won't work if you are trying to create a heap.
source to share
The algorithm, if deployed correctly, can of course be used as part of the heap building algorithm. This is complicated a little by the fact that when building the heap, the root of the subsurface being recovered is not the beginning of the array, which affects the implementation of sift-up (it must stop when the current element of the array is reached, not continue to the bottom of the heap).
It should be noted that the algorithm has the same asymptotic characteristics as the standard heap repair algorithm; however, this is likely due to fewer comparisons. This is in part because the standard heap recovery algorithm is called after replacing the heap root (largest element) for the last element of the heap array.
The last item is not necessarily the smallest item in the heap, but it will likely be close to the bottom. After swapping, the standard algorithm will move the swap down to log 2N times, and each step requires two comparisons; because the element is likely to be near the bottom of the heap, the maximum number of comparisons will be done most of the time. But sometimes only two or four comparisons can be made.
Instead, the "sloppy" algorithm begins by moving the "hole" from the top of the heap to somewhere near the bottom (log 2 N comparisons) and then moving the last element up until it finds it at home, which usually only takes a few comparisons (but in the worst case can take almost log 2 N comparison).
Now, in case heapify
, heap recovery is done not with the last element in the sub, but with a previously invisible element taken from the original vector. This doesn't really change the average performance analysis much, because if you start heap recovery with a random element, instead of an element that might be small, the expected number of sifters is still close to the maximum. (Half of the heap is at the last level, so the probability of needing the maximum number of sieves for a random element is half.)
While a sloppy algorithm (probably) improves the number of element comparisons, it increases the number of element movements. The classical algorithm performs at most log 2 N swaps, while a sloppy algorithm does at least log 2N swaps, plus additional swaps during the sift-up. (In both cases, swaps can be improved to move without inserting a new element until its actual position is known, halving the amount of memory storage.)
As a postscript, I could not find a link to your "sloppy" algorithm. In general, when you ask about the proposed algorithm, it is best to include a link.
source to share
There is a linear time algorithm for building the heap. I believe what the author meant is that using this approach to create the heap is inefficient and there are no better algorithms. Of course, you can build a heap by adding items one by one using the described strategy - you just can do better.
source to share