C implementation of http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf

MiniMax Heap

/* Author: Stetsenko Makar */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>

#define MIN 1
#define MAX 2

typedef long long ll;

typedef struct {
    int size;
    ll *data;
} MinMaxHeap;

void swapInts(ll *a, ll *b) {
    ll tmp = *a;
    *a = *b;
    *b = tmp;
}

/******* MinMaxHeap METHODS ********/
/* referenced
 * http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf 
 */

char getLvl(int id) {
    id++;
    int lvl = log2(id);
    if (lvl % 2 == 0) return MIN;
    else return MAX;
}

int getMinMaxChildGrandChildIndex(MinMaxHeap *heap, int root, int d) {
    int i, minIndex = heap->size;
    for (i = 0; i < 6; i++) {
        int index = ((i > 1)?4:2)*root + i + 1;
        if (index < heap->size) {
            if (minIndex == heap->size) minIndex = index;
            else minIndex = (d*heap->data[minIndex] > d*heap->data[index]) ? index : minIndex;
        }
    }
    return minIndex;
}

/**
  Moves element down the heap, d = 1 when on min lvls or -1 when on max
  d=+-1 helps avoid writing the function with reversed relational operators for
  MAX levels
  */
void siftDownMinMax(MinMaxHeap *heap, int start, int d) {
    int root = start;
    if (root*2+1 >= heap->size) return; // if root has no children

    int m = getMinMaxChildGrandChildIndex(heap, root, d);

    if (m > root*2+2) {
        if (d*heap->data[m] < d*heap->data[root]) {
            swapInts(&(heap->data[root]), &(heap->data[m]));
            int parent = (m-1)/2;
            if (m >= 0 && d*heap->data[m] > d*heap->data[parent])
                swapInts(&(heap->data[m]), &(heap->data[parent]));
            siftDownMinMax(heap, m, d);
        }
    } else {
        if (d*heap->data[m] < d*heap->data[root])
            swapInts(&(heap->data[m]), &(heap->data[root]));
    }
}

/**
 * Moves element down the heap reconstructing heap prop
 */
void siftDown(MinMaxHeap *heap, int start) {
    if (getLvl(start) == MIN)
        siftDownMinMax(heap, start, 1);
    else 
        siftDownMinMax(heap, start, -1);
}

void siftUpMaxMin(MinMaxHeap *heap, int start, int d) {
    if (start <= 2) return; // no granparents on lvl 0 and 1
    
    int gp;
    if ((gp = ((start-1)/2 - 1)/2) >= 0) {
        if (d*heap->data[start] < d*heap->data[gp]) {
            swapInts(&(heap->data[gp]), &(heap->data[start]));
            siftUpMaxMin(heap, gp, d);
        }
    }
}

/**
 * Moves element up the heap reconstructing heap prop
 */
void siftUp(MinMaxHeap *heap, int start) {
    int parent;

    if (getLvl(start) == MIN) {
        // if start has a parent and it's smaller then start
        if ((parent=(start-1)/2) >= 0 && heap->data[start] > heap->data[parent]) {
            swapInts(&(heap->data[start]), &(heap->data[parent]));
            siftUpMaxMin(heap, parent, -1); // MAX
        } else siftUpMaxMin(heap, start, 1); // MIN
    } else {
        if ((parent=(start-1)/2) >= 0 && heap->data[start] < heap->data[parent]) {
            swapInts(&(heap->data[start]), &(heap->data[parent]));
            siftUpMaxMin(heap, parent, 1);
        } else siftUpMaxMin(heap, start, -1);
    }
}

/**
 * checks heap property and prints conflicting nodes
 */
void checkHeapProp(MinMaxHeap *heap) {
    int i;
    for (i = 0; i < heap->size; i++) {
        int lc = 2*i+1, rc = 2*i+2;
        int d = (getLvl(i)==MIN) ? 1 : -1;
        if (lc < heap->size && d*heap->data[lc] < d*heap->data[i])
            printf("Validation: lc:%lld root:%lld\n", heap->data[lc], heap->data[i]);
        if (rc < heap->size && d*heap->data[rc] < d*heap->data[i])
            printf("Validation: rc:%lld root:%lld\n", heap->data[lc], heap->data[i]);
    };
}

/**
 * Creates heap from an array of size count
 */
MinMaxHeap* heapify(ll *arr, int count) {
    MinMaxHeap* heap = malloc(sizeof(MinMaxHeap));
    assert(heap != NULL);
    
    heap->data = arr;
    heap->size = count;
    
    // start is assigned the index in a of the last parent node
    int start = (count - 2 ) / 2;
    
    while (start >= 0) {
        // sift down the node at index start to the proper place such that all nodes below
        // the start index are in heap order
        siftDown(heap, start);
        start -= 1;
    }
    
    //checkHeapProp(heap);
    
    return heap;
}

void insert(MinMaxHeap *heap, ll element) {
    //if (heap->data[0] == element) return;
    heap->data[heap->size] = element;
    heap->size++;
    siftUp(heap, heap->size-1);
    //checkHeapProp(heap);
}

void removeMin(MinMaxHeap *heap) {
    swapInts(&(heap->data[0]), &(heap->data[heap->size-1]));
    heap->size -= 1;
    siftDown(heap, 0);
    //checkHeapProp(heap);
}

void removeMax(MinMaxHeap *heap) {
    int index;

    if (heap->size == 1) index = 0;
    else if (heap->size == 2) index = 1;
    else index = (heap->data[1] < heap->data[2]) ? 2 : 1;

    swapInts(&(heap->data[index]), &(heap->data[heap->size-1]));
    heap->size -= 1;
    siftDown(heap, index);
    //checkHeapProp(heap);
}

ll peekMin(MinMaxHeap *heap) { return heap->data[0]; }
ll peekMax(MinMaxHeap *heap) {
    if (heap->size == 1) return heap->data[0];
    else if (heap->size == 2) return heap->data[1];
    else return (heap->data[1] < heap->data[2]) ? heap->data[2] : heap->data[1];
}

MinMaxHeap* createHeap(int size) {
    MinMaxHeap *heap = malloc(sizeof(MinMaxHeap));
    ll *data  = malloc(sizeof(ll) * size);
    
    heap->data = data;
    heap->size = 0;
    
    return heap;
}

void deleteHeap(MinMaxHeap *heap) {
    free(heap->data);
    free(heap);
}

void deleteHeapWithArr(MinMaxHeap *heap) {
    free(heap);
}

int main(int argc, const char *argv[])
{
    int n = 20053, i;
    MinMaxHeap *heap = createHeap(n);
    srand(time(NULL));
    for (i = 0; i < n - 1; i++) {
        int command = rand() % 11;
        if (command <= 5 || heap->size == 0) {
            int num = rand() % 100000;
            num *= (rand() % 3 == 1)?-1:1;
            insert(heap, num);
            printf("Insert(%d)\n", num);
        }
        else if (command <= 7 && heap->size > 0) {
            printf("ExtractMax\n");
            removeMax(heap);
        } else if (heap->size > 0) {
            printf("ExtractMin\n");
            removeMin(heap);
        }
    }

    deleteHeap(heap);
    return 0;
}