c语言实现最大堆

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Heap {
    int array[1024];
    int size;
    int capacity;
} Heap;

void heap_create(Heap *p)
{
    memset(p->array, 0x00, sizeof(p->array));

    p->capacity = 1024;
    p->size = 0;
}

void heap_adjust_down(int *a, int n, int parent)
{
    int child = 2 * parent;
    int t;

    while(child < n)
    {
        if(child + 1 < n && a[child] < a[child+1])
        {
            child++;
        }

        if(a[child] > a[parent])
        {
            t = a[child];
            a[child] = a[parent];
            a[parent] = t;
            parent = child;
            child = 2 * parent;
        }
        else
        {
            break;
        }
    }
}

void heap_adjust_up(int *a, int n, int child)
{
    int parent = (child) / 2;
    int t;

    while(child > 0)
    {
        if(a[child] > a[parent])
        {
            t = a[child];
            a[child] = a[parent];
            a[parent] = t;
            child = parent;
            parent = (child) / 2;
        }
        else
        {
            break;
        }
    }
}

void heap_push(Heap *p, int x)
{
    p->array[p->size] = x;
    p->size++;

    heap_adjust_up(p->array, p->size, p->size-1);
}

int heap_top(Heap *p)
{
    return p->array[0];
}

int heap_pop(Heap *p)
{
    int c = p->array[0];

    p->array[0] = p->array[p->size-1];
    p->array[p->size-1] = 0;

    p->size--;

    heap_adjust_down(p->array, p->size, 0);

    return c;
}

int main()
{
    Heap heap;
    char cmd[64];
    int n;
    int t;
    int i;

    heap_create(&heap);

    scanf("%d", &n);

    for(i=0; i<n+1; i++)
    {
        memset(cmd, 0x00, sizeof(cmd));

        fgets(cmd, 63, stdin);

        if(strncmp(cmd, "push", 4) == 0)
        {
            t = atoi(cmd+5);

            heap_push(&heap, t);
        }
        else if(strncmp(cmd, "pop", 3) == 0)
        {
            if(heap.size != 0)
            {
                t = heap_pop(&heap);

                printf("%d\n", t);
            }
            else
            {
                printf("empty\n");
            }
        }
        else if(strncmp(cmd, "top", 3) == 0)
        {
            if(heap.size != 0)
            {
                t = heap_top(&heap);

                printf("%d\n", t);
            }
            else
            {
                printf("empty\n");
            }
        }
    }

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
5
push 45
push 44
push 43
pop
45
pop
44