Generic Heap

#define HEAP_SIZE (1 << 15)
typedef int tVal;
typedef int tKey;
typedef struct HeapNode {
    tKey key;
    tVal val;
    int index;
} HeapNode;
HeapNode vHeapNodes[HEAP_SIZE];
HeapNode* lastHeapNode;
HeapNode* heap[HEAP_SIZE];
int heapSize;
void initHeap() {
    lastHeapNode = vHeapNodes - 1;
    heapSize = 0;
}
void heapUpdateNode(HeapNode* node) {
    int index = node->index;
    tKey key = node->key;
    while (index) {
        int parentIndex = (index - 1) >> 1;
        HeapNode* parent = heap[parentIndex];
        if (parent->key >= key) break;
        heap[index] = parent;
        parent->index = index;
        index = parentIndex;
    }
    for (;;) {
        int childIndex = (index << 1) | 1;
        if (childIndex >= heapSize) break;
        HeapNode* child = heap[childIndex];
        int secondChildIndex = childIndex + 1;
        if (secondChildIndex < heapSize) {
            HeapNode* secondChild = heap[secondChildIndex];
            if (secondChild->key > child->key) {
                child = secondChild;
                childIndex = secondChildIndex;
            }
        }
        if (child->key <= key) break;
        heap[index] = child;
        child->index = index;
        index = childIndex;
    }
    heap[index] = node;
    node->index = index;
}
HeapNode* heapPush(tVal val, tKey key) {
    HeapNode* node = ++lastHeapNode;
    node->val = val;
    node->key = key;
    node->index = heapSize ++;
    heapUpdateNode(node);
    return node;
}
tVal heapPop() {
    HeapNode* head = heap[0];
    -- heapSize;
    if (heapSize) {
        HeapNode* node = heap[heapSize];
        node->index = 0;
        heapUpdateNode(node);
    }
    return head->val;
}