0
$\begingroup$

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-heapified". This to me seems somewhat inefficient. We have more knowledge from the maxheap, namely, that the root node and one of its children are the 2 largest elements in the maxheap (assuming the children of the root have different values). So why not pluck off the root node and the larger child, and THEN re-heapify? That should reduce the number of reheapify "calls". What we are attempting here is to exploit the fact that we have knowledge of where the 2 largest elements are in a maxheap so it makes sense to grab BOTH of them, not just the root node. Also when swapping in the 2 elements from the tail end of the tree, part of the enhancement is to put the larger of those 2 as the new root node and the smaller as the replacement for the other element (the larger child of the root we "popped"). Reason being that we might get lucky and maintain the maxheap property this way (as can be seen from the second example trace), thus avoiding excessive sifting down.

So I am wondering if and how this possible tweak will change the analysis of heapsort and if (and by how much) it may (or may not) speed up heapsort on say 1 million random integers (or some reasonable number where a speedup or slowdown can be noticed easily).

Hand trace results of (9,5,8,4,1,6,2). This is the input array I would like sorted in ascending order using Heapsort. I cannot draw out the heaps here so I will just list them in the parenthesis for each step and the operations are pop (pull an item out of the heap from the root position and place it one position past the end of the heap, thus holding that position as part of the sorted output), top (move an item from the tail end of the heap to the root), and swap (exchange positions of 2 items that are both still in the heap). Note that data will not be "clobbered" and it is assumed if we move data into a certain position where data already is, that "old" data is saved somewhere temporarily for later use (such as to be moved elsewhere in the heap).

So first using classic Heapsort:

(9,5,8,4,1,6,2) this is already a maxheap.

step 1. pop 9 (according to the rules above, the 2 will not be clobbered)
step 2. top 2
(2,5,8,4,1,6) 9 this is NOT a maxheap.

step 3. swap 2 and 8
(8,5,2,4,1,6) 9 this is STILL not a maxheap.

step 4. swap 2 and 6
(8,5,6,4,1,2)

step 5. pop 8
step 6. top 2 (notice 2 is bouncing between root & leaf often which is bad).
(2,5,6,4,1) 8 9

step 7. swap 2 and 6 (again).
(6,5,2,4,1)

step 8. pop 6
step 9. top 1
(1,5,2,4) 6 8 9

step 10: swap 5 and 1.
(5,1,2,4) 6 8 9

step 11: swap 1 and 4.
(5,4,2,1)

step 12: pop 5
step 13: top 1
(1,4,2) 5 6 8 9

step 14: swap 1 and 4.
(4,1,2)

step 15: pop 4
step 16: top 2
(2,1) 4 5 6 8 9

step 17: pop 2
step 18: top 1
1 2 4 5 6 8 9 (DONE in 18 steps).

General comments about classic Heapsort... There seems to be too much readjusting of the heap because of low values being put at the root of the heap and that induces many required swaps which although those reform the maxheap, they waste some processor time.

Now look what happens if instead of just popping 1 element (the root node) at each maxheap, we instead pop the root AND the larger child (if one exists):

(note that we grab the 2 last entries still in the maxheap and the larger of those becomes the new root and the smaller fills in the space of the 2nd element we popped). So we introduce a new function called nrc which stands for new root child and means to put an element as the new child of the root which had one of its children (the larger) popped (so we are filling in the missing space)

Starting with the same (9,5,8,4,1,6,2) which is already a maxheap...

Step 1: pop 9 (the root node)
Step 2: top 6 (move the larger of 2 last leaves in the heap as the new root)
Step 3: pop 8 (the larger of the 2 children of the root)
Step 4: nrc 2 (fill in the tree position of the larger child of the root)

(6,5,2,4,1) 8 9 (notice how we filled 2 spots in the sorted portion of the array in one pass before checking if we have to reheapify the entire tree).

Luckily, this modified tree is STILL a maxheap so we pluck 2 more elements.

Step 5: pop 6
Step 6: top 4
Step 7: pop 5
Step 8: nrc 1

(4,1,2) 5 6 8 9

Luckily, this modified tree is STILL a maxheap so we pluck 2 more elements.
Step 9: pop 4
Step 10: pop 2
Step 11: top 1 (only 1 element left so that is the new root and we are done)

1 2 4 5 6 8 9 DONE in only 11 steps! This is 7 fewer steps than classic Heapsort took and there are 0 swaps in this example. That is somewhat by luck, but also because we are putting the higher of the last 2 remaining elements still in the heap as the new root, and cuz we are plucking 2 elements from the heap at each pass (so there are less iterations that might require a swap). It seems this first example is showing promising signs for this "double pop" modification. Also, one of the nice things about this mod is that it should be a fairly straightforward implementation change once you have the classic heapsort code working properly.

$\endgroup$
  • 1
    $\begingroup$ Have you benchmarked heapsort with your tweaks? $\endgroup$ – Apass.Jack May 5 at 5:13
  • 1
    $\begingroup$ I suppose running benchmarks would be your job first. $\endgroup$ – gnasher729 May 5 at 16:03
  • $\begingroup$ Yes I may have to try implementing Heapsort in an interpreted language cuz that is all I have here on my computer. I can start with maybe 1000 random integers and count up the number of sift downs and swaps using the conventional Heapsort, and then try it with my proposed tweaks and see if there is any improvement. I was just hoping someone either had or could type in Heapsort in a compiled language to see if there is any speed increase because compiled and interpreted give different apparent differences in speed increases for optimizations. $\endgroup$ – David James May 5 at 16:10
  • $\begingroup$ Not rhetorical because I am not only making a statement about how classic Heapsort is somewhat inefficient, I am also asking if people here think it will improve the average case runtime of it, either by somehow testing it on a computer or computing it mathematically or both. $\endgroup$ – David James May 7 at 1:13
  • 2
    $\begingroup$ As it is written, your question is very hard to understand. I would suggest you take some time to neatly write down the proposed algorithm for easier inspection not only by yourself but other people as well. $\endgroup$ – Juho May 7 at 10:21
2
$\begingroup$

If you pluck your largest child in place of root then you have to pluck something in now empty space after your max child. If you pluck its max child... you need to apply it until leaf, so this change will result in different order of same operations or break indexing scheme for heap.

Heap uses properties of complete binary tree, if you just move pointer, then you have broken indexing scheme and need to remember new place of root and its children. If you continue this way, you have to fix your heap or keep indices, so more memory and more work.

Please check how it really works, prove it doesn't break anything and make proper average case analysis, because some random test (as requested, by some random people on internet) with relatively big input does not prove speedup, it only shows that given sample benefits from it. Making more random tests is still not enough, it is pure luck or not random enough PRNG.

$\endgroup$
  • 2
    $\begingroup$ To downvoter, it is really pointless to downvote without comment, your own answer or any sign what to change. If you do not care enough, what it gives you? $\endgroup$ – Evil May 5 at 21:40
  • $\begingroup$ To me it seems if you want to test if a modified algorithm is faster than the original (as we are trying to determine here), just turn off any compiler optimizations, turn off caching on your computer... and just use a reasonable size input array so it finishes in a reasonable amount of time but not just milliseconds. For example, if original Heapsort took 5 seconds and modified Heapsort took 4 seconds on the same exact data with compiler optimizations and caching off, that would be worth investigating more since it is a 20% improvement. Then I would try other input data and look for patterns. $\endgroup$ – David James May 6 at 6:23
  • 1
    $\begingroup$ disabling compiler optimizations doesn't make testing any better $\endgroup$ – Bulat May 6 at 9:13
  • $\begingroup$ One way is to force test all those 5 cases both ways (with and without caching), thus making 10 test scenarios, and log them all. Then try tweaking the code and try them all again. Some patterns should emerge. I fail to see how a "double popping" algorithm that uses more knowledge of the data can underperform a more naive algorithm (classic Heapsort) that effectively wastes useful information. Also classic Heapsort is inefficient by always swapping in the last element in the heap as the new root. That is naive and we can easily do better than that. It was probably done for simplicity. $\endgroup$ – David James May 6 at 17:18
  • $\begingroup$ Another way to test all these cases is to have the computer generate a small amount of test data (say 1000 random numbers), and sort them using Heapsort, but iterate this test maybe 100,000 times, recording the data for the slowest, fastest, and average cases for analysis after it is finished. That is a way to let the computer tell you what data makes the algorithm run the best, worst, and average. Then taking those 3 (or more) test data samples, run them thru the tweaked code and see what happens since if it outperforms in all 3, then the tweak is not overly sensitive to any particular data. $\endgroup$ – David James May 6 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.