- size_t m = n;
- size_t i;
-
- while (m > 0)
- {
- /* Invariant: a[m..n-1] is a heap. */
- m--;
- for (i = m; 2*i+1 < n; )
- {
- if (2*i+2 < n
- && fde_compare (ob, a[2*i+2], a[2*i+1]) > 0
- && fde_compare (ob, a[2*i+2], a[i]) > 0)
- {
- SWAP (a[i], a[2*i+2]);
- i = 2*i+2;
- }
- else if (fde_compare (ob, a[2*i+1], a[i]) > 0)
- {
- SWAP (a[i], a[2*i+1]);
- i = 2*i+1;
- }
- else
- break;
- }
- }
- while (n > 1)
+ int m;
+
+ /* Expand our heap incrementally from the end of the array, heapifying
+ each resulting semi-heap as we go. After each step, a[m] is the top
+ of a heap. */
+ for (m = n/2-1; m >= 0; --m)
+ frame_downheap (ob, fde_compare, a, m, n);
+
+ /* Shrink our heap incrementally from the end of the array, first
+ swapping out the largest element a[0] and then re-heapifying the
+ resulting semi-heap. After each step, a[0..m) is a heap. */
+ for (m = n-1; m >= 1; --m)