heap.c

Go to the documentation of this file.

 
#include "heap.h"
 
void heap_insert(t_gen d,t_gen data);
t_gen heap_extract_root(t_gen d);
void heap_build(t_gen d);
void heap_sort(t_gen d);
int heap_len(t_gen d);
void heap_print(t_gen d);
bool heap_empty(t_gen d);
bool heap_full(t_gen d);
t_gen heap_update_key(t_gen d, t_gen val, int idx);
void destroy_heap(t_gen d);
 
 
t_gen create_heap(char *name, t_gen data, int size, e_heaptype htype, t_dparams *prm)
{
    t_heap *h = get_mem(1, sizeof(t_heap));
 
    // Initailze heap Params
    h->name       = name;
    h->type       = htype;
    h->data       = data;
    h->size       = size;
    h->count      = 0;
    
    // Initailze heap routines
    h->insert     = heap_insert;
    h->extract    = heap_extract_root;
    h->build      = heap_build;
    h->sort       = heap_sort;
    h->len        = heap_len;
    h->update     = heap_update_key;
    h->full       = heap_full;
    h->empty      = heap_empty;
    h->print      = heap_print;
    h->destroy    = destroy_heap;
 
    // Initailze datatype based operations req for prop working of heap
    h->cmpr       = prm->cmpr;
    h->cmpr_idx   = prm->cmpr_idx;
    h->swap_idx   = prm->swap_idx; 
    h->copy_idx   = prm->copy_idx;
    h->get_idx    = prm->get_idx;
    h->print_data = prm->print_data;
    
    return (t_gen)h;
}
 
 
bool heap_full(t_gen d)
{
    t_heap *h = (t_heap*)d;
 
    return (h->count >= h->size);
}
 
bool heap_empty(t_gen d)
{
    t_heap *h = (t_heap*)d;
 
    return (h->count == 0);
}
 
void heapify_up(t_heap *h, int idx)
{
    int parent;
    e_cmpr cmp_res;
    // exit condition depending type of heap
    cmp_res = (h->type == eMAX_HEAP)? eGREAT : eLESS;
 
    for (parent = (idx - 1) / 2; idx; parent = (idx - 1) / 2) {
        // Heap prop satisfied parent </> child for min/max heap
        // else swap parent and child and go one up
        if (h->cmpr_idx(h->data, parent, idx) == cmp_res) {
            break;
        } else {
            h->swap_idx(h->data, parent, idx);
        }
        idx = parent;
    }
}
 
void heap_insert(t_gen d,t_gen data)
{
    t_heap *h = (t_heap*)d;
 
    if (h->count >= h->size) {
        LOG_WARN("HEAP", "%s: HEAP_FULL\n",h->name);
        return;
    }
    
    h->copy_idx(h->data, h->count, data);
    heapify_up(h, h->count);
    h->count++;
}
 
void heapify(t_heap *h, int idx)
{
    int parent,lchild,rchild;
    e_cmpr cmp_res;
    
    // exit condition depending type of heap
    cmp_res = (h->type != eMAX_HEAP)? eGREAT : eLESS;
    lchild = rchild = 0;
    for (parent = idx; rchild <= h->count; ) {
        lchild = (2 * idx)+1; rchild = (2 * parent) + 2;
        // Heap prop satisfied parent </> child for min/max heap
        // else parent and child and go one up
        if (lchild < h->count && h->cmpr_idx
                (h->data, parent, lchild) == cmp_res) {
            parent = lchild;
        }
        if (rchild < h->count && h->cmpr_idx
                (h->data, parent, rchild) == cmp_res) {
            parent = rchild;
        }
    
        // if parent has changed swap parent with idx
        if (idx != parent) {
            h->swap_idx(h->data, parent, idx);
            idx = parent;
        } else {
            break;
        }
    }   
}
 
void heap_build(t_gen d)
{
    t_heap *h = (t_heap*)d;
    int idx;
    
    h->count = h->size;
    for(idx = h->size/2; idx >= 0; idx--) {
        heapify(h, idx);
    }
}
 
 
t_gen heap_extract_root(t_gen d)
{
    t_heap *h = (t_heap*)d;
    t_gen data = NULL;
 
    if (h->count == 0) {
        LOG_WARN("HEAP", "%s: HEAP EMPTY\n",h->name);
        return data;
    }
    
    // Root is swapped with last node in heap
    // temp store root at last heap location
    h->count--;
    h->swap_idx(h->data, 0, h->count);
 
    // heapify to preserve heap prop
    heapify(h, 0);
    
    //Ref to previous heap root is returned
    data = h->get_idx(h->data, h->count);
    
    return data;
}
 
void heap_sort(t_gen d)
{
    t_heap *h = (t_heap*)d;
    int i,n = (h->count-1);
    
    // build heap
    h->build(h);
 
    // Move the current root to last
    // sorted but in traverse in reverse order
    for(;h->count;) {
        // Root to be deleted is swapped with last node in heap
        h->count--;
        h->swap_idx(h->data, 0, h->count);
        // heapify to preserve heap prop
        heapify(h, 0);
    }
}
 
t_gen heap_update_key(t_gen d, t_gen val, int idx)
{
    t_heap *h = (t_heap*)d;
    t_gen tmp = NULL;
    e_cmpr cmp_res;
    
    if (idx < 0 || idx >= h->count) {
        LOG_WARN("HEAP", "%s: idx out of bound\n",h->name);
        return tmp;
    }
 
    // exit condition depending type of heap
    cmp_res = (h->type != eMAX_HEAP)? eGREAT : eLESS;
    tmp = h->get_idx(h->data, idx);
    
    // If new val '<'/'>' previous val or min/max heap
    // then heapify up else heapify down
    if (h->cmpr(tmp, val) == cmp_res) {
        h->copy_idx(h->data, idx, val);
        heapify_up(h, idx);
    }
    else {
        h->copy_idx(h->data, idx, val);
        heapify(h, idx);
    }
 
    return tmp;
}
 
int heap_len(t_gen h)
{
    return ((t_heap*)h)->count;
}
 
void destroy_heap(t_gen d)
{
    t_heap *h = (t_heap*)d;
    
    free_mem(h);
}
 
/*  @brief
 *  Util function to get type of heap in string
 *  @param type  - heap Type
 *  @return String of heap type
*/
char * get_heaptype_name(e_heaptype type)
{
    switch (type) {
        case eMIN_HEAP:
            return "MIN_HEAP";
        case eMAX_HEAP:
            return "MAX_HEAP";
    }
 
    return "UNDEFINED";
}
void heap_print(t_gen d)
{
    t_heap *h = (t_heap*)d; 
    int i;
 
    printf("%s:%s {count: %d} {size: %d}\n[ ",h->name, 
            get_heaptype_name(h->type), h->count, h->size);
    for (i = 0; i < h->size; i ++) {
        h->print_data(h->get_idx(h->data, i));
        printf(" ");
    }
    printf("]\n");
}