+\f
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the first COUNT - 1 elements of these form a heap, followed by
+ a single element not part of the heap. This function adds the
+ final element, forming a heap of COUNT elements in ARRAY.
+ Uses COMPARE to compare elements, passing AUX as auxiliary
+ data. */
+void
+push_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t i;
+
+ expensive_assert (count < 1 || is_heap (array, count - 1,
+ size, compare, aux));
+ for (i = count; i > 1; i /= 2)
+ {
+ unsigned char *parent = first + (i / 2 - 1) * size;
+ unsigned char *element = first + (i - 1) * size;
+ if (compare (parent, element, aux) < 0)
+ SWAP (parent, element, size);
+ else
+ break;
+ }
+ expensive_assert (is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ the children of ARRAY[idx - 1] are heaps, but ARRAY[idx - 1]
+ may be smaller than its children. This function fixes that,
+ so that ARRAY[idx - 1] itself is a heap. Uses COMPARE to
+ compare elements, passing AUX as auxiliary data. */
+static void
+heapify (void *array, size_t count, size_t size,
+ size_t idx,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ for (;;)
+ {
+ size_t left = 2 * idx;
+ size_t right = left + 1;
+ size_t largest = idx;
+
+ if (left <= count
+ && compare (first + size * (left - 1),
+ first + size * (idx - 1), aux) > 0)
+ largest = left;
+
+ if (right <= count
+ && compare (first + size * (right - 1),
+ first + size * (largest - 1), aux) > 0)
+ largest = right;
+
+ if (largest == idx)
+ break;
+
+ SWAP (first + size * (idx - 1), first + size * (largest - 1), size);
+ idx = largest;
+ }
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function moves the
+ largest element in the heap to the final position in ARRAY and
+ reforms a heap of the remaining COUNT - 1 elements at the
+ beginning of ARRAY. Uses COMPARE to compare elements, passing
+ AUX as auxiliary data. */
+void
+pop_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+
+ expensive_assert (is_heap (array, count, size, compare, aux));
+ SWAP (first, first + (count - 1) * size, size);
+ heapify (first, count - 1, size, 1, compare, aux);
+ expensive_assert (count < 1 || is_heap (array, count - 1,
+ size, compare, aux));
+}
+
+/* Turns ARRAY, which contains COUNT elements of SIZE bytes, into
+ a heap. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+void
+make_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ size_t idx;
+
+ for (idx = count / 2; idx >= 1; idx--)
+ heapify (array, count, size, idx, compare, aux);
+ expensive_assert (count < 1 || is_heap (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. Initially
+ all COUNT elements form a heap. This function turns the heap
+ into a fully sorted array. Uses COMPARE to compare elements,
+ passing AUX as auxiliary data. */
+void
+sort_heap (void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ unsigned char *first = array;
+ size_t idx;
+
+ expensive_assert (is_heap (array, count, size, compare, aux));
+ for (idx = count; idx >= 2; idx--)
+ {
+ SWAP (first, first + (idx - 1) * size, size);
+ heapify (array, idx - 1, size, 1, compare, aux);
+ }
+ expensive_assert (is_sorted (array, count, size, compare, aux));
+}
+
+/* ARRAY contains COUNT elements of SIZE bytes each. This
+ function tests whether ARRAY is a heap and returns 1 if so, 0
+ otherwise. Uses COMPARE to compare elements, passing AUX as
+ auxiliary data. */
+int
+is_heap (const void *array, size_t count, size_t size,
+ algo_compare_func *compare, void *aux)
+{
+ const unsigned char *first = array;
+ size_t child;
+
+ for (child = 2; child <= count; child++)
+ {
+ size_t parent = child / 2;
+ if (compare (first + (parent - 1) * size,
+ first + (child - 1) * size, aux) < 0)
+ return 0;
+ }
+
+ return 1;
+}