Can this "double pop" Heapsort variation speed up sorting on average?

Question

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.

Answer 1

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.

• Apply Floyd's heap construction

• Use bottom-up heapsort

• C/C++

• Test again other inputs such as sorted or reverse-sorted.

• Grab three or more elements a time.

Answer 2

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.

Answer 3

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