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

#include "introprog_heap.h"

/* Reserviere Speicher für einen Heap
 *
 * Der Heap soll dabei Platz für capacity Elemente bieten.
 *
 * Um konsistent mit den Parametern für malloc zu sein, ist
 * capacity als size_t (entspricht unsigned long auf x86/64)
 * deklariert.
 * Da es sauberer ist, sind auch alle Indizes in dieser Aufgabe
 * als size_t deklariert. Ob man size_t oder int als Index für
 * ein Array verwendet, macht in der Praxis (auf x86/64) nur
 * bei Arrays mit mehr als 2.147.483.647 Elementen einen
 * Unterschied.
 */
heap* heap_create(size_t capacity) {

    int array[capacity];
    heap* h = (heap*)malloc((2+capacity)*sizeof(int));
        h->elements = array;
        h->size = 0;
        h->capacity = capacity;
        return h;
}

/* Stellt die Heap Bedingung an Index i wieder her
 *
 * Vorraussetzung: Der linke und rechte Unterbaum von i
 * erfüllen die Heap-Bedingung bereits.
 */
void heapify(heap* h, size_t i) {

    int biggest = i;
    int leftc = 2*i;
    int rightc = 2*i+1;

    if(leftc <= h->size && h->elements[leftc] > h->elements[biggest]){
        biggest = leftc;
    }
    if(rightc<= h->size && h->elements[rightc] > h->elements[biggest]){
        biggest = rightc;
    }
    if(biggest != i){
        int temp = biggest;
        h->elements[biggest] = h->elements[i];
        h->elements[i] = h->elements[temp];
        heapify(h, biggest);
    }
}





/* Holt einen Wert aus dem Heap
 *
 * Wenn der Heap nicht leer ist, wird die größte Zahl
 * zurückgegeben. Wenn der Heap leer ist, wird -1 zurückgegeben.
 */
int heap_extract_max(heap* h) {

    if(h->size <= 0){
        return -1;
    }
    int max = h->elements[0];
    h->elements[0] = h->elements[h->size];
    h->size = h->size-1;
    heapify(h, h->elements[0]);
    return max;
}

/* Fügt einen Wert in den Heap ein
 *
 * Wenn der Heap bereits voll ist, wird -1 zurückgegeben.
 */
int heap_insert(heap* h, int key) {

    h->size = h->size+1;
    int i = h->size;
    int j = h->size;
    if(h->size%2==1){
        j--;
    }
    while(i > 1 && h->elements[j/2] < i){
        h->elements[i] = h->elements[j/2];
        i = j/2;
    }
    h->elements[i] = key;
    return h->elements[i];
}

/* Gibt den Speicher von einem Heap wieder frei
 */
void heap_free(heap* h) {
    free(h);
}