#include "minheap.h"

int heap_parent ( int index ) { return index / 2; }
int heap_left ( int index ) { return index * 2; }
int heap_right ( int index ) { return index * 2 + 1; }

void heap_swap ( heap_t *heap, int from, int to ) 
{
    heapitem_t temp_swap = heap->heap[to];
    heap->heap[to] = heap->heap[from];
    heap->heap[from] = temp_swap;
}

void heap_minHeapify ( heap_t *heap, int index ) 
{
    int rightnode, leftnode, smallest;
    leftnode = heap_left ( index );
    rightnode = heap_right ( index );
    
    if ( leftnode <= heap->size && heap->heap[leftnode].dist < heap->heap[index].dist )
        smallest = leftnode;
    else
        smallest = index;
    
    if ( rightnode <= heap->size && heap->heap[rightnode].dist < heap->heap[smallest].dist )
        smallest = rightnode;
    
    if ( smallest != index ) 
    {
        heap_swap ( heap, index, smallest );
        heap_minHeapify ( heap, smallest ); 
    }  
}       

void heap_buildMinHeap ( heap_t *heap ) 
{
    int count;
    for ( count = heap->size; count >= 0; count-- )
        heap_minHeapify ( heap, count );
}

void heap_addItem ( heap_t *heap, heapitem_t new_item )
{
    heap->heap[heap->size] = new_item;
    heap->size++;
    heap_buildMinHeap(heap);   
}