优先队列(堆) 数据结构与算法分析C语言实现

#ifndef _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(int X, PriorityQueue H);
int DeleteMin(PriorityQueue H);
int FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif

#define MinPQSize (5)
#define MinData (-10000)
struct HeapStruct
{
    int Capacity;
    int Size;
    int *Elements;
};

PriorityQueue Initialize(int MaxElements)
{
    PriorityQueue H;
    if (MaxElements < MinPQSize)
    {
        printf("Priority queue size is too small");
        exit(EXIT_FAILURE);
    }
    H = (PriorityQueue)malloc(sizeof(struct HeapStruct));
    if (H == NULL)
    {
        printf("Out of spacen");
        exit(EXIT_FAILURE);
    }
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements = (int *)malloc(sizeof(int) * MaxElements + 1);
    if (H->Elements == NULL)
    {
        printf("Out of spacen");
        exit(EXIT_FAILURE);
    }
    H->Elements[0] = MinData;
    return H;
}

void Destroy(PriorityQueue H)
{
    if (H != NULL)
    {
        free(H->Elements);
        free(H);
    }
}

void MakeEmpty(PriorityQueue H)
{
    H->Size = 0;
}

void Insert(int X, PriorityQueue H)
{
    int i;
    if (IsFull(H))
    {
        printf("Priority queue is fulln");
        return;
    }
    for ( i = ++H->Size; H->Elements[i/2] > X; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

int DeleteMin(PriorityQueue H)
{
    int i, Child;
    int MinElement, LastElement;
    if (IsEmpty(H))
    {
        printf("Priority queue is emptyn");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for ( i = 1; i*2 <= H->Size ; i = Child)
    {
        Child = i * 2;
        if (Child != H->Size && H->Elements[Child]>H->Elements[Child+1])
            Child++;
        if (H->Elements[Child] < LastElement)
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

int FindMin(PriorityQueue H)
{
    return H->Elements[1];
}

int IsEmpty(PriorityQueue H)
{
    return H->Size == 0;
}

int IsFull(PriorityQueue H)
{
    return H->Size == H->Capacity;
}