HW2_binary_heap

#include <cstdio>
#include <cstdlib>

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

void siftup(int * heap, int i)
{
    while (heap[i] < heap[(i - 1) / 2])
    {
        swap(heap[i], heap[(i-1)/2]);
        i = (i - 1) / 2;
    }
}

void siftdown(int * heap, int i, int n)
{
    int left = 0, right = 0, j = 0;
    while (2 * i + 1 < n)
    {
        left = 2 * i + 1;
        right = 2 * i + 2;
        j = left;
        if (right < n && heap[right] < heap[left])
            j = right;
        if (heap[i] < heap[j])
            return;
        swap(heap[i], heap[j]);
        i = j;
    }
}

void add(int * heap, int i, int &n)
{
    n++;
    heap[n - 1] = i;
    siftup(heap, n - 1);
}

int delete_min(int *heap, int &n)
{
    int min = heap[0];
    heap[0] = heap[n - 1];
    n--;
    siftdown(heap, 0, n);
    return min;
}

int main()
{
    int n = 5;
    int heap[] = { 1, 2, 3, 5, 6, 0 };
    add(heap, 4, n);
    printf("%i\n", delete_min(heap, n));
    return 0;
}