Skip to main content
21 of 21
added 89 characters in body
David James
  • 124
  • 2
  • 16

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

David James
  • 124
  • 2
  • 16