Priority Queue Definition

Priority queues are data structures with at least two operations: Insert and Delete Min.

Binary heap definition

The abstract concept of binary heap is a fully filled binary tree (the bottom may have exceptions), because the relationship between father and son is very regular (elements in any position i, father in abs(i/2), left son in 2i, and son in 2i+1, multiplied by left-shift and right-shift operation), it can be implemented by array without needing pointers (linked list).

Algorithmic Implementation

/* Elr Heap Int Source */
#include <stdio.h>
#include <stdlib.h>
#include "elr_heap_int.h"

#define parent(x) (x >> 1)
#define left(x) (x << 1)
#define right(x) (x << 1 + 1)

pHeap elrInitHeap(int capaticy) {
    pHeap s;

    s = malloc(sizeof(sHeap));
    if (s == NULL) {
        printf("out of space!");
    }

    s->data = malloc(sizeof(long long int) * (capaticy + 1));
    if (s->data == NULL) {
        printf("out of space!");
    }

    s->capacity = capaticy;
    s->size = 0;
    s->data[0] = -1;

    return s;
}

void elrFreeHeap(pHeap info) {
    if (info != NULL) {
        free(info->data);
        free(info);
    }
}

int elrIsHeapEmpty(pHeap info) {
    return info->size == 0;
}

int elrIsHeapFull(pHeap info) {
    return info->size == info->capacity;
}

void elrPushHeap(pHeap info, long long int value) {
    int i;

    if (elrIsHeapFull(info)) {
        printf("full heap");
    } else {
        for (i = ++info->size; info->data[parent(i)] > value; i = parent(i)) {
            info->data[i] = info->data[parent(i)];
        }
        info->data[i] = value;
    }
}

long long int elrFindHeapMin(pHeap info) {
    if (elrIsHeapEmpty(info)) {
        printf("empty heap");
        return info->data[0];
    } else {
        return info->data[1];
    }
}

long long int elrDeleteHeapMin(pHeap info) {
    int i, child;
    long long int min, last;

    if (elrIsHeapEmpty(info)) {
        printf("empty heap");
        return info->data[0];
    } else {
        min = info->data[1];
        last = info->data[info->size--];
        for (i = 1; left(i) <= info->size; i = child) {
            child = left(i);
            if ((child != info->size) && (info->data[child] >= info->data[child + 1])) {
                child++;
            }
            if (last > info->data[child]) {
                info->data[i] = info->data[child];
            } else {
                break;
            }
        }
        info->data[i] = last;
        return min;
    }
}