优先级队列(大顶堆)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MinPQsize 10
#define MaxData 32768
struct heapStruct
{
    int capacity;
    int size;
    int *eles;
};

typedef struct heapStruct *priorityQueue;
priorityQueue initialize(int Maxelements)
{
    priorityQueue H;
    if (Maxelements < MinPQsize)
    {
        printf("Priority Queue size is too small");
        exit(1);
    } 
    H= (priorityQueue)malloc(sizeof(struct heapStruct));
    if (H == NULL)
        exit(1);
        
    /* allocate the array plus one extra for sentinel */
    H->eles = (int *)malloc((Maxelements + 1) * sizeof(int));
    if (H->eles == NULL)
        exit(1);
        
    memset(H->eles, 0, (Maxelements + 1) * sizeof(int));
    
    H->capacity = Maxelements;
    H->size = 0;
    H->eles[0] = MaxData;
    return H;
} 

bool isFull(priorityQueue H)
{
    return H->size == H->capacity;
}

bool isEmpty(priorityQueue H)
{
    return H->size == 0;
}

void destroy(priorityQueue H)
{
    free(H->eles);
    free(H);
} 

/* H->eles[0] is a sentinel */

/* push heap */
/*    将最大值调整到第一个H->eles[1]     */
void insert(int X, priorityQueue H)
{
    int i;
    if (isFull(H))
    {
        printf("Priority queue is full");
        exit(1);
    }
    for ( i = ++H->size; H->eles[i / 2] < X; i /= 2)
        H->eles[i] = H->eles[i / 2];
    H->eles[i] = X;
}

/* pop heap */
int deleteMax(priorityQueue H)
{
    int i, child;
    int MaxElement, LastElement;
    if (isEmpty(H))
    {
        printf("priority queue is empty");
        exit(1);
    } 
    
    MaxElement = H->eles[1];
    LastElement = H->eles[H->size--];
    
    for (i = 1; i * 2 <= H->size; i = child)
    {
        /* find bigger child */
        child = i * 2;
        if (child != H->size - 1 && H->eles[child + 1] > H->eles[child])
            child++;
        /* precolate one level */
        if (LastElement < H->eles[child])
            H->eles[i] = H->eles[child];
        else
            break;
    } 
    H->eles[i] = LastElement;
    return MaxElement;
} 

#define leftChild(i) (2*(i) + 1)
void percolate(int *arr, int i, int N)
{
    int tmp, child;

    for (tmp = arr[i]; leftChild(i) < N; i = child)
    {
        child = leftChild(i);
        if (child != N - 1 && arr[child + 1] > arr[child])
            child++;
   
        if (arr[child] > tmp)
            arr[i] = arr[child];
        else
            break;
    }

    arr[i] = tmp;
}

// 将一段现有数据转化为一个heap
void make_heap(int *arr, int N)
{
    for (int i = N / 2; i >= 0; i--)
    percolate(arr, i, N);
}

int main(void)
{
    int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
    priorityQueue T = NULL;
    
    T = initialize(20);
    int i;
    
    for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        insert(arr[i], T);
        
    for (i = sizeof(arr) / sizeof(arr[0]); i > 0; i--)
            arr[i - 1] = deleteMax(T); //不断对heap进行pop操作，便可达到排序效果sort_heap
            
    for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        printf("%d ", arr[i]);
    printf("\n");
    int arr2[] = {15, 2, 7, 20, 32, 28, 18, 34};
    make_heap(arr2, sizeof(arr2) / sizeof(arr2[0]));
    for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
        printf("%d ", arr2[i]);
    return 0;
}