"[Data Structure] Min Heap"

Two Charactics of Min Heap

A Min Heap is represented as a binary tree, this binary tree has two characteristics:

  1. value of a parent node are smaller than which of its child nodes
  2. the binary tree is a complete binary tree
  3. a complete binary tree is defined as:
    • each level of complete binary tree is completely filled, except possibly the last level
    • nodes of the last level are as far left as possible
    • a complete binary tree can be efficiently implemented using an array

Implementation in C

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

#ifdef DEBUG
#define DBG(fmt, args...)   printf(fmt, ##args)
#else
#define DBG(fmt, args...)
#endif

#define SWAP(a, b)  { \
    int tmp = a; \
    a = b; \
    b = tmp; \
}

struct min_heap {
    size_t capacity;
    int *a;
    size_t size;
};

struct min_heap *min_heap_initialize(size_t capacity)
{
    struct min_heap *mh;

    mh = calloc(1, sizeof(struct min_heap));
    assert(mh);

    mh->capacity = capacity;
    mh->a = calloc(capacity + 1, sizeof(int));
    assert(mh->a);
    mh->size = 0;

    return mh;
}

void min_heap_finalize(struct min_heap *mh)
{
    free(mh->a);
    free(mh);
}

#ifdef DEBUG
void min_heap_show(struct min_heap *mh)
{
    size_t i;

    printf("[ ");
    for (i = 1; i <= mh->size; i++)
        printf("%d ", mh->a[i]);
    printf("]\n");
}
#else
void min_heap_show(struct min_heap *mh) { }
#endif

void min_heap_siftup(struct min_heap *mh)
{
    size_t n = mh->size;
    int *a = mh->a;

    while (n > 1) {
        if (mh->a[n] >= mh->a[n/2])
            break;
        SWAP(a[n], a[n/2]);
        n = n/2;
    }
}

void min_heap_insert(struct min_heap *mh, int val)
{
    assert(mh->size < mh->capacity);

    mh->a[++mh->size] = val;
    min_heap_siftup(mh);
}

void min_heap_siftdown(struct min_heap *mh)
{
    size_t n = 1;
    int *a = mh->a;
    /* smallest index among [ parent, left child, right child ] */
    size_t k;

    while (n <= mh->size / 2) {
        k = n;

        if (a[2*n] < a[n])
            k = 2*n;

        if (2*n + 1 <= mh->size && a[2*n+1] < a[k])
            k = 2*n + 1;

        if (k == n)
            break;

        SWAP(a[n], a[k]);
        n = k;
    }
}

int min_heap_pop(struct min_heap *mh)
{
    int top = mh->a[1];

    mh->a[1] = mh->a[mh->size--];
    min_heap_siftdown(mh);

    return top;
}

bool is_sorted(int a[], size_t size)
{
    size_t i;

    for (i = 0; i < size - 1; i++) {
        if (a[i] > a[i + 1])
            return false;
    }

    return true;
}

int main(int argc, const char *argv[])
{
    int a[65536];
    size_t size = sizeof(a) / sizeof(a[0]);
    struct min_heap *mh;
    size_t i;

    srandom(time(NULL));
    for (i = 0; i < size; i++) {
        a[i] = random();
    }

    mh = min_heap_initialize(size);

    for (i = 0; i < size; i++) {
        DBG("insert %d\n", a[i]);
        min_heap_insert(mh, a[i]);
        min_heap_show(mh);
    }

    for (i = 0; i < size; i++) {
        a[i] = min_heap_pop(mh);
        DBG("pop %d\n", a[i]);
        min_heap_show(mh);
    }

    min_heap_finalize(mh);

    for (i = 0; i < size; i++) {
        DBG("%d ", a[i]);
    }
    DBG("\n");

    if (is_sorted(a, size)) {
        printf("TEST PASS\n");
        return 0;
    } else {
        printf("TEST FAIL\n");
        return -1;
    }

    return 0;
}

References

[1] https://en.wikipedia.org/wiki/Binary_tree