heap.c

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

#define c1(i) 2*i + 1
#define c2(i) 2*i + 2
#define p(i) (i-1)/2

struct Heap {
    int *heap;
    int size;
    int capacity;
};

typedef struct Heap Heap;

void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

void heap_print(Heap *h)
{
    printf("size: %d\n-------------\n", h->size);
    for(int i = 0; i < h->size; i++)
    {
        printf("%d  ", h->heap[i]);
        if(!((i+1)&(i+2))) printf("\n");
    }
    printf("\n-------------\n");
}

void heapify(Heap *h, int index)
{
    int c1 = c1(index) >= h->size ?  -1 : c1(index);
    int c2 = c2(index) >= h->size ?  -1 : c2(index);
    int min_i = index;

    if (c2 > 0)
        min_i = h->heap[c1] < h->heap[c2] ? c1 : c2;
    else if (c1 > 0)
        min_i = c1;
    else
        return;

    if(h->heap[index] > h->heap[min_i]) {
        swap(&h->heap[index], &h->heap[min_i]);
        heapify(h, min_i);
    }
}

Heap* create_heap(int *a, int n, int capacity)
{
    Heap *h = (Heap*)malloc(sizeof(Heap));
    h->heap = (int*)malloc(capacity*sizeof(int));
    h->size = n;
    h->capacity = capacity;
    for(int i = 0; i < n; i++)
        h->heap[i] = a[i];

    for (int i = (h->size - 2) / 2; i >= 0; i--)
        heapify(h, i);

    return h;
}

void heap_insert(Heap *h, int x)
{
    if (h->size == h->capacity)
        return;
    h->heap[h->size++] = x;
    for (int i = h->size - 1; i > 0; i = p(i))
        if(h->heap[p(i)] > h->heap[i])
            swap(&h->heap[i], &h->heap[p(i)]);
}

int heap_delete(Heap *h)
{
    int x = h->heap[0];
    h->heap[0] = h->heap[--h->size];
    heapify(h, 0);
    return x;
}

void heap_sort(Heap *h)
{
    int s = h->size;
    for(int i = 0; i < s; i++)
        printf("%d ", heap_delete(h));
}

int main()
{
    int a[23] = {2,4,6,1,2,5,3,10,0,1,4,23,543,34,23,11,545,656,7,3,1,5,0};
    Heap *h = create_heap(a, 23, 100);
    while(1){
        int d;
        char operation[100];
        scanf("%s", operation);
        if (!strcmp(operation, "i"))
        {
            scanf("%d", &d);
            heap_insert(h,d);
        }
        else if (!strcmp(operation, "d"))
        {
            printf("del : %d\n", heap_delete(h));
        }
        else if (!strcmp(operation, "p"))
        {
            heap_print(h);
        }
        else if (!strcmp(operation, "s"))
        {
            heap_sort(h);
        }
    }
    return 0;
}