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.