Why does my code only work with these two empty print statements?

Question

void siftdown(struct heap *H, int i) {

      int pIndex, lcIndex;
      int siftKey = H->nodes[i];
      int spotFound = 0;
      pIndex = i;

       printf(" ");
      //  printf("first:%d ", H->size);

      while (2 * pIndex + 1 <= H->size - 1 && spotFound == 0) {
        if (2 * pIndex < H->size - 1 &&
            (H->nodes[2 * pIndex + 1] < H->nodes[2 * pIndex + 2])) {
          lcIndex = 2 * pIndex + 2;
          // printf("second:%d ", H->size);
        } else {
          lcIndex = 2 * pIndex + 1;
          // printf("third:%d ", H->size);
        }
        if (siftKey < H->nodes[lcIndex]) {
          H->nodes[pIndex] = H->nodes[lcIndex];
          pIndex = lcIndex;
          // printf("fourth:%d ", H->size);
        } else {
          spotFound = 1;
          // printf("fifth:%d ", H->size);
        }
      }
      H->nodes[pIndex] = siftKey;
    }
    void makeHeap(int n, struct heap *H) {
      H->size = n;
      printf(" ");
      // printf("sixth:%d ", H->size);
      for (int i = floor(n / 2); i >= 0; i--) {
        //printf("\n%d %d", i, H->nodes[i]);
        siftdown(H, i);
      }
    }`

Im doing a array implementation of a heap and between the makeHeap to siftDown pass the heaps size becomes 0, unless these two empty print statements are present.

Im assuming that the heap->size call is reading from a register rather than fetching from memory but I don't really know how to fix it.

Answer 1

You have an unchecked access to H->nodes[2 * pIndex + 2] in this part of your code:

  while (2 * pIndex + 1 <= H->size - 1 && spotFound == 0) {
    if (2 * pIndex < H->size - 1 &&
        (H->nodes[2 * pIndex + 1] < H->nodes[2 * pIndex + 2])) {

The condition 2 * pIndex < H->size - 1 is not the right one. This was already checked by the while condition, so when executed, this will always evaluate to true. You need to check whether the node has a right child, with this condition: 2 * pIndex + 2 < H->size.

Because this is not checked, you may get into a situation where lcIndex is out of range, and eventually that makes pIndex out of range, leading to a write to that location with H->nodes[pIndex] = siftKey;. This results in undefined behaviour. For instance, if that memory location happens to be used by size, then this assignment alters the size.

I would also harmonise all these boundary checks, using < H->size and not <= H->size - 1 and other variants.

Note a problem, but in makeHeap you don't need to floor as the division is an integer division. You can also do with one iteration less, starting at n/2-1.

So:

void siftdown(struct heap *H, int i) {
  int parentIndex = i;
  int childIndex = i * 2 + 1;
  int siftKey = H->nodes[i];

  while (childIndex < H->size) {
    if (childIndex + 1 < H->size && H->nodes[childIndex] < H->nodes[childIndex + 1]) {
      childIndex++;
    }
    if (siftKey >= H->nodes[childIndex]) {
      break;
    }
    H->nodes[parentIndex] = H->nodes[childIndex];
    parentIndex = childIndex;
    childIndex = 2 * parentIndex + 1;
  }
  H->nodes[parentIndex] = siftKey;
}

void makeHeap(int n, struct heap *H) {
  H->size = n;
  for (int i = n / 2 - 1; i >= 0; i--) {
    siftdown(H, i);
  }
}