数据结构-堆

typedef enum{false, true} bool;
typedef int ElementType;

typedef struct HNode *Heap;
struct HNode {
    ElementType *Data;
    int Size;
    int Capacity;
};
typedef Heap MaxHeap;
typedef Heap MinHeap;

#define MAXDATA 1000

MaxHeap CreateHeap(int MaxSize) {
    MaxHeap H   = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data     = (ElementType*)malloc(sizeof(ElementType)*(MaxSize+1));
    H->Size     = 0;
    H->Capacity = MaxSize;
    H->Data[0]  = MAXDATA;
    // ReadInput(H);
    return H;
}

bool IsFull(MaxHeap H) {
    return H->Size == H->Capacity;
}

bool IsEmpty(MaxHeap H) {
    return !H->Capacity;
}

bool Insert(MaxHeap H, ElementType X) {
    if (IsFull(H)) {
        puts("Full!");
        return false;
    }
    int i = ++ H->Size;
    for (; X > H->Data[i/2]; i /= 2)
        H->Data[i] = H->Data[i/2];
    H->Data[i] = X;
    return true;
}

ElementType DeleteMax(MaxHeap H) {
    if (IsEmpty(H)) {
        puts("Empty Heap!");
        return false;
    }
    ElementType MaxItem = H->Data[1];
    ElementType X = H->Data[H->Size --];
    int i, j;
    for (i = 1; i*2 <= H->Size; i = j) {
        j = i*2;
        if (j != H->Size && H->Data[j] < H->Data[j+1])
            ++ j;
        if (X >= H->Data[j]) break;
        else
            H->Data[i] = H->Data[j];
    }
    H->Data[i] = X;
    return MaxItem;
}

void PrecDown(MaxHeap H, int p) {
    ElementType X = H->Data[p];
    int i, j;
    for (i = p; i*2 <= H->Size; i = j) {
        j = i*2;
        if (j != H->Size && H->Data[j] < H->Data[j+1])
            ++ j;
        if (X >= H->Data[j]) break;
        else
            H->Data[i] = H->Data[j];
    }
    H->Data[i] = X;
}

void BulidHeap(MaxHeap H) {
    int i;
    for (i = H->Size/2; i > 0; -- i)
        PrecDown(H, i);
}