2
$\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 comparisons and movements. 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$
8
  • 1
    $\begingroup$ Have you benchmarked heapsort with your tweaks? $\endgroup$
    – John L.
    May 5, 2019 at 5:13
  • 1
    $\begingroup$ I suppose running benchmarks would be your job first. $\endgroup$
    – gnasher729
    May 5, 2019 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$ May 5, 2019 at 16:10
  • 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, 2019 at 10:21
  • 1
    $\begingroup$ To me it seems that anyone that understands how classic Heapsort works should fairly easily be able to understand my mods to it. In a nutshell, I am taking a single pop algorithm and making it a double pop algorithm. I recommend drawing out the actual heaps on paper for my example traces and you will easily see them. One paper for classic Heaport for my example, I had 12 different trees. For the double pop trace, I only needed 3 trees and it finished. That is a BIG difference! $\endgroup$ May 7, 2019 at 10:36

3 Answers 3

2
$\begingroup$

This technique of "double pop" belongs to the general idea of loop unrolling. Similarly, we could have "double selection" variant of selection sort, which will select the smallest and second smallest elements together while scanning the unsorted elements. We could also have "double insertion" variant of insertion sort, which will insert two elements together, where we can compare two elements first.


As promised by OP, it is quite easy to follow his pseudocode, despite the difference that indices in the pseudocode start from one while indices in my Java or C++ start from 0.

I made several improvements after porting the procedure Heapsort2 to java, which I renamed to doublePopHeapsort.

  • all four variables, lg1, lc, lg2 and lcp are eliminated.
  • the loop variable i and the conditional check if (i >= 3) are removed.

Here is my code for the method doublePopHeapsort, that is valid both in Java and in C/C++. The method buildMaxHeap and heapify, not listed here, are the same for both ordinary heapsort and doublePopHeapsort.

    // A is the given array of length n.
    void doublePopHeapsort() {
        if (n <= 1) return;

        buildMaxHeap();

        /* Grabs 2 largest numbers in maxheap each pass */
        while (--n > 2) {
            swap(0, n);
            --n;
            if (A[1] >= A[2]) {
                swap(1, n);
                heapify(1);
            } else {
                swap(2, n);
                heapify(2);
            }
            heapify(0);
        }

        /* regular heapsort to handle no more than 3 unsorted elements. */
        do {
            swap(0, n);
            heapify(0);
        } while (--n > 0);

Here on repl.it is my benchmark program that compares the performance of a version of ordinary heapsort and its corresponding version of double-pop heapsort. Hit the "run" button and see the results. However, the results over there fluctuates too much to be reliable at all, because, I assume, it runs on a shared machine with forceful time-sharing management.

Instead, I use my local compute. My computer is a "2.2 GHz Quad-Core Intel Core i7" with "16 GB 1600 MHz DDR3". Java version is "Java HotSpot(TM) 64-Bit Server VM (build 14.0.1+7, mixed mode, sharing)". I have run the benchmark program for many hours using various parameters. Here are typical results for arrays of integers that are randomly distributed over an interval.

   "Array size" is the size of array to be sorted. 
   "Variations" is the number different arrays. 
   "repetitions" is the number of times the same array is sorted.
   "ordinary total" is the total time used by ordinary heapsort.  
   "double-pop total" is the total time used by double-pop heapsort.  

       Array size: 10
       Variations: 10000
       repetition: 43429
   ordinary total: 41944 ms
 double-pop total: 36771 ms
 average speed-up: 14.1%

       Array size: 100
       Variations: 10000
       repetition: 2171
   ordinary total: 43297 ms
 double-pop total: 40672 ms
 average speed-up: 6.5%

       Array size: 1000
       Variations: 1000
       repetition: 1447
   ordinary total: 100123 ms
 double-pop total: 97193 ms
 average speed-up: 3.0%

       Array size: 10000
       Variations: 1000
       repetition: 108
   ordinary total: 107437 ms
 double-pop total: 105253 ms
 average speed-up: 2.1%

       Array size: 100000
       Variations: 100
       repetition: 86
   ordinary total: 108346 ms
 double-pop total: 106668 ms
 average speed-up: 1.6%

       Array size: 1000000
       Variations: 100
       repetition: 7
   ordinary total: 121017 ms
 double-pop total: 119892 ms
 average speed-up: 0.9%

       Array size: 10000000
       Variations: 10
       repetition: 6
   ordinary total: 147249 ms
 double-pop total: 145372 ms
 average speed-up: 1.3%

The above data indicates convincingly that double-pop heapsort is faster than ordinary heapsort. The improvement ranges from more than 10% for very short arrays to about 1% for large arrays.

It might be argued that the improvement should be better for larger array since the time saving of double-pop heapsort over the ordinary heapsort comes from less call to the heapify method. The cost of heapify depends largely on the depth of the leaf elements of the heap. However, as seen from the data above, the improvement as a percentage decreases as the size of array increases. Further analysis is needed to understand why.


I have also written a program that counts the number of swaps used. Here are the typical results, again for arrays of integers that are randomly distributed over an interval.

      Array size: 10
      Variations: 1000000
  ordinary total: 25109682 swaps
double-pop total: 21020795 swaps
    swap savings: 19.5%

      Array size: 100
      Variations: 100000
  ordinary total: 82995859 swaps
double-pop total: 73891119 swaps
    swap savings: 12.3%

      Array size: 1000
      Variations: 100000
  ordinary total: 990804913 swaps
double-pop total: 931577233 swaps
    swap savings: 6.4%

      Array size: 10000
      Variations: 1000
  ordinary total: 1115005054 swaps
double-pop total: 1050774991 swaps
    swap savings: 6.1%

      Array size: 100000
      Variations: 1000
  ordinary total: 2689951677 swaps
double-pop total: 2575706461 swaps
    swap savings: 4.4%

      Array size: 1000000
      Variations: 100
  ordinary total: 4594778322 swaps
double-pop total: 4430536135 swaps
    swap savings: 3.7%

      Array size: 10000000
      Variations: 100
  ordinary total: 26978266897 swaps
double-pop total: 26314038249 swaps
    swap savings: 2.5%

The percentages of swap saving of double-pop over ordinary heapsort are roughly compatible with the typical result above of performance. Higher savings implies greater speed-up, roughly.

It is expected the performance of double-pop heapsort may vary on different situations such as size of input array, type of array elements, programming language and the compiled code, cpu and memory type, cold or warmed-up run. Although it is not a surprise that it may take more time for double-pop heapsort than an ordinary heapsort to sort a particular array, double-pop heapsort is faster than heapsort in general.


Further investigation may include the following and more.

$\endgroup$
9
  • $\begingroup$ Well that is encouraging that it seems to be slightly faster for random data I assume. I saw similar results (of about 3%) in an interpreted language. Yes I should have mentioned I used 1 indexing, not 0 indexing, however that is easy to code around (just use the 0 position as a placeholder and use the same indexing as me). Thanks for checking this for me. I suspected it would be quicker but not enough to warrant changing textbooks and even really mentioning it as a significant performance tweak. However, to squeeze out that last bit of speed, it helps. $\endgroup$ Apr 28, 2020 at 1:31
  • $\begingroup$ Yes I checked it out thanks. Interesting results. It would have been cool to test something other than just random numbers like semi-sorted for example. Also, I had a variation of double pop heapsort where I put the larger of the 2 swapped in numbers at the root and the smaller in the child of the root that we popped but the extra checking for that actually slowed it down some. The motivation for this double pop was that we have information available to us of where the 2 largest numbers in the maxheap are, so we may as well grab both. Grabbing only the root is wasting some information. $\endgroup$ Apr 28, 2020 at 1:58
  • $\begingroup$ I should have put a simple positive answer to the question at the top, "Yes!" (However, it might not be wise in non-libray coding to replace ordinary heapsort by double-pop heapsort.) By the way, I should probably grab 2 elements as well when there are 3 elements left, in line with "double pop". $\endgroup$
    – John L.
    Apr 29, 2020 at 3:14
  • 1
    $\begingroup$ Grabbing 3 elements at a time is not easy like grabbing 2. 2 is a "gift" because we know in a maxheap, it is the root and one of the children. Determining which is the 3rd largest is not so easy. You would have to check 3 other elements I think (the previously unchosen child of the root vs up to 2 children of the child of the root that was chosen as the 2nd largest element). The "triple" (in most cases) comparison there might slow down any possible savings. For example, suppose our maxheap array was 9,8,5,7,4,3,1. We can easily grab 9 and 8 (double pop) but we have to compare 5,7,and 4. $\endgroup$ May 1, 2020 at 15:01
  • 1
    $\begingroup$ I suspect grabbing 3 elements would be a "wash" (no faster than grabbing 2). 3 might even be slower. It shouldn't be much harder to implement so it might be interesting to try. Also, what if the heap had up to 4 children instead of up to 2 children? Then for very large arrays, the tree depth would be reduced. For example, an array of size 1,048,576 would be 20 levels deep for a regular complete binary tree, but only 10 levels deep if each node has 4 children. $\endgroup$ May 1, 2020 at 15:17
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$
8
  • 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, 2019 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$ May 6, 2019 at 6:23
  • 1
    $\begingroup$ disabling compiler optimizations doesn't make testing any better $\endgroup$
    – Bulat
    May 6, 2019 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$ May 6, 2019 at 17:18
  • 1
    $\begingroup$ For a small amount of data to test these 2 algorithms on, it seems like a fair test to just time both since both will be heavily cached by the computer they are being tested on. Another interesting way to analyze the improvement would be to count up the number of swaps during re-heapify. In the hand trace examples here, there are 6 swaps for classic Heapsort and 0 for "double pop" Heapsort. One example is not indicative of average performance but it does illustrate that ALL swaps can be made to go away in some cases (this is probably rare). I will try implementing both and count swaps. $\endgroup$ May 7, 2019 at 10:26
1
$\begingroup$

Actually I tried implementing this and I do see a slight (3%) speedup in most cases, but I used an interpreted language so I am not sure if similar results would happen for a compiled language. My main test was I used 100,000 randomly generated integer numbers in the range 0 to 99,999 and tried sorting them with both "classic" heapsort and my modified heapsort. All of the test data is integer numbers only (no floating point, no strings...).

The code just grabs the 2 "highest" numbers in the maxheap, then calls Heapify on those 2 nodes, making sure the swapped numbers in those positions don't violate the maxheap property. Depending on which child of the root is larger, it either calls Heapify(2) or Heapify (3), followed by Heapify(1).

Results: "Classic" Heapsort = 16.63 seconds runtime. My "double pop" variation: 16.15 seconds (about 3% quicker in actual speed). The computer I used to test was an old Dell inspiron 1420 laptop slowed to 1.0 Ghz (but capable of up to 1.67 Ghz), with 4GB main memory.

Other test results were as follows (classic first then mine): (in seconds)

Already sorted (in order): 17.4 vs. 16.85.
Backwards sorted : 15.84 vs. 15.37.
All same numbers: 1.308 vs. 1.44 (mine is actually slower in this case).
Small range random numbers (0-99): 16.5 vs. 16.03.

n = # of elements in the unsorted heap (will get decremented as we sort)
FI = shorthand for ENDFOR.
LOCAL means those variables are only visible within the procedure defined.
You will need to generate your own random numbers for testing.

Here is the "classic" Heapsort pseudocode:


PROCEDURE Heapsort()

LOCAL i

BuildMaxHeap()

FOR i = n TO 1 STEP -1
...Swap(1, i)
...n = n - 1
...Heapify(1)
ENDFOR i

RETURN


PROCEDURE Swap(p1, p2) ..... /* p1 and p2 are the array positions to swap */

LOCAL temp

temp = A[p1]
A[p1] = A[p2]
A[p2] = temp

RETURN


PROCEDURE BuildMaxHeap

LOCAL i

FOR i = INT(n/2) TO 1 STEP -1
...Heapify(i)
ENDFOR i

RETURN


PROCEDURE Heapify(i)

LOCAL left, right, max

left = i + i
right = left + 1

IF (left <= n) AND (A[left] > A[i])
...max = left
ELSE
...max = i
FI

IF (right <= n) AND (A[right] > A[max])
...max = right
FI

IF max # i
...Swap(i, max)
...Heapify(max)
FI

RETURN


"This is my modified Heapsort which grabs 2 numbers at a time"
lg1 is the first largest number we want.
lg2 is the 2nd largest number we want.
lc = largest child.
lcp = largest child position.


PROCEDURE Heapsort2()  /* Grabs 2 largest numbers in maxheap each pass */

LOCAL i, temp, lc, lcp, lg1, lg2

FOR i = n TO 1 STEP - 1

  IF (i >= 3)  /* make sure there are at least 2 children to check */
    lg1 = A[1]  
    lc = Larger(A[2], A[3])  /* larger valued child of root node */  
    lg2 = IIF(lc = A[2], lc, A[3])  
    lcp = IIF(lc = A[2], 2, 3)  
    A[1] = A[i]  
    A[i] = lg1  
    i = i - 1
    A[lcp] = A[i]  
    A[i] = lg2  
    n = n - 2     /* the unsorted heap is now 2 elements smaller */  
    Heapify(lcp)  /* re-heapify the larger child we swapped data with */  
    Heapify(1)  

  ELSE  /* regular Heapsort to handle when there are < 3 unsorted nodes left. */
    Swap(1, i)
    n = n - 1
    Heapify(1)
  FI  

ENDFOR i

RETURN

$\endgroup$
5
  • $\begingroup$ This pseudo-code should work as written, ported to your implementation language. I tried to keep the p-code "generic" and fairly easy to port (although not the easiest to understand). This is code I took from elsewhere and then modified it to work with the "double pop" method. I am curious to see what happens when someone else benchmarks 1 million random numbers using some other language like c or even a more modern one. Results using an interpreted language like I did vs. a complied language might have different results. Maybe little or no difference in a complied language for example. $\endgroup$ Apr 20, 2020 at 1:44
  • $\begingroup$ Also, it would be very easy to change this code to put the larger of the 2 numbers coming from the last 2 elements of the heap to be such that the larger becomes the new root value and the smaller become the new child value (either in position 2 or 3 depending on which was larger to begin with). I tried the mod in the interpreted language and it slowed it down slightly because of the extra checks, but in a complied (fast) language, it might be beneficial to try it both way (with and without that feature). With 1 million random integers, you should be able to tell if it helps or not. $\endgroup$ Apr 20, 2020 at 15:17
  • $\begingroup$ @John L. - Double pop heapsort (not double hop), and I gave the correct working pseudocode so there should be nothing to debug, just port to the language of choice. That pseudocode was taken from actual working code. $\endgroup$ Apr 27, 2020 at 0:22
  • $\begingroup$ If you like, we can chat at collabedit.com/94rcb. $\endgroup$
    – John L.
    Apr 27, 2020 at 1:20
  • $\begingroup$ @John L. - thanks for your great analysis on this. I am happy there is at least some speedup. I would be interested in doing a 4 child heapsort variation next. That is, each node will have 4 children except it is optional for the "bottom right" of the tree. It would increase the "branching factor" of the tree, making it less "deep". Not sure what the impact on actual speed would be. It might be a good research paper for someone in the field. Heapsort is a great concept but is clearly not optimal. With some good analysis, I am confident it can be sped up even more than just a few %. $\endgroup$ May 7, 2020 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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