common STheapify: fix incorrect construction of heap

Note that this fix, while intended to address #2529 (closed), turned out to be the root cause of #2391 (closed) too.

---

This bug was introduced in 711b470c and causes certain inputs to not result in a correctly constructed heap. For example, [10, 9, 13, 15, 17, 99, 3, 12, 21] is incorrectly “heapified” into [3, 21, 12, 13, 99, 17, 15, 10, 9].

It is difficult to test internal code like this, so instead I extracted its logic into a separate program.¹ Either Kimon’s fix or my own are sufficient to address this problem, but I have committed my own here which I believe is an improved simplification.

Gitlab: fixes #2391 (closed), fixes #2529 (closed)
Reported-by: icktoofay
Reported-by: Kimon Papahadjopoulos

¹ The C program that follows:

    #include <assert.h>
    #include <stddef.h>
    #include <stdio.h>

    static void heapify(int *heap, int size, int i) {
      int left, right, smallest;
      do {
        left = 2 * (i + 1) - 1;
        right = 2 * (i + 1);
    #ifdef ORIGINAL
        if (left < size && heap[left] < heap[i])
          smallest = left;
        else
          smallest = i;
        if (right < size && heap[right] < heap[smallest])
          smallest = right;
        else
          smallest = i;
    #elif defined(KIMON_FIX)
        if (left < size && heap[left] < heap[i])
          smallest = left;
        else
          smallest = i;
        if (right < size && heap[right] < heap[smallest])
          smallest = right;
    #elif defined(MATT_FIX)
        smallest = i;
        if (left < size && heap[left] < heap[smallest])
          smallest = left;
        if (right < size && heap[right] < heap[smallest])
          smallest = right;
    #else
    #error "define one of ORIGINAL, KIMON_FIX, or MATT_FIX"
    #endif
        if (smallest != i) {
          int temp = heap[i];
          heap[i] = heap[smallest];
          heap[smallest] = temp;
          i = smallest;
        } else
          break;
      } while (i < size);
    }

    static void buildheap(int *heap, int size) {
      for (int i = size / 2; i >= 0; i--)
        heapify(heap, size, i);
    }

    static int extractmin(int *heap, int *size) {
      int rv = heap[0];
      heap[0] = heap[*size - 1];
      --*size;
      heapify(heap, *size, 0);
      return rv;
    }

    int main(void) {
      int order[] = {10, 9, 13, 15, 17, 99, 3, 12, 21};
      int size = sizeof(order) / sizeof(order[0]);

      buildheap(order, size);

      for (int i = 0; (size_t)i < sizeof(order) / sizeof(order[0]); i++)
        printf("%d ", extractmin(order, &size));
      printf("\n");

      return 0;
    }