优先队列定义

优先队列是至少有两种操作的数据结构：插入 (Insert), 删除最小者 (DeleteMin)。

二叉堆定义

二叉堆抽象概念是一个完全填满的二叉树 (底层可能有例外)，由于父子关系很有规律 (任意位置 i 上的元素，父亲在 abs(i/2), 左儿子在 2i 上，有儿子在 2i+ 1 上，用左移右移操作实现乘除 )，可以用数组实现而不需要指针 (链表)。

算法实现

/* 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;
    }
}