Heap by C

heap.c

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

#include "heap.h"

Heap *initHeap(int maxSize) {
  Heap *h = malloc(sizeof(Heap));
  if (h == NULL) {
    return NULL;
  }
  int *val = malloc(sizeof(int) * (size_t)maxSize);
  if (val == NULL) {
    free(h);
    return NULL;
  }
  h->val = val;
  h->size = 0;
  h->maxSize = maxSize;
  return h;
}

void heapPush(Heap *h, int v) {
  h->size++;
  assert(h->size <= h->maxSize);
  h->val[h->size - 1] = v;

  for (int i = h->size - 1; i > 0 && h->val[i] < h->val[parent(i)]; i = parent(i)) {
    swap(&h->val[i], &h->val[parent(i)]);
  }
}

int heapPop(Heap *h) {
  int ret = h->val[0];
  swap(&h->val[0], &h->val[h->size - 1]);
  h->size--;
  heapify(h, 0);
  return ret;
}

void heapify(Heap *h, int i) {
  while (1) {
    int smallest = i;
    if (left(i) < h->size && h->val[left(i)] < h->val[smallest]) {
      smallest = left(i);
    }
    if (right(i) < h->size && h->val[right(i)] < h->val[smallest]) {
      smallest = right(i);
    }
    if (smallest == i) {
      break;
    } else {
      swap(&h->val[i], &h->val[smallest]);
      i = smallest;
    }
  }
}

void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

int parent(int i) {
  return (i - 1) / 2;
}

int left(int i) {
  return 2 * i + 1;
}

int right(int i) {
  return 2 * i + 2;
}

heap.h

typedef struct heap {
  int *val;
  int size, maxSize;
} Heap;

Heap *initHeap(int maxSize_);

void heapPush(Heap *h, int v);

int heapPop(Heap *h);

void heapify(Heap *h, int i);

void swap(int *x, int *y);

int parent(int i);
int left(int i);
int right(int i);