Binary Heap

heaptree.c

//! gcc -o heaptree.bin heaptree.c -W -Wall -O0 -g -std=gnu99 

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int htree_value_t;
typedef int (*htree_cmp_t)( const htree_value_t *, const htree_value_t *);

typedef struct htree {
    htree_value_t *data;
    int  n;
    int  alloced;
    /* htree_cmp_t cmp; */
} *htree_t;

htree_t htree_create();
bool htree_isnull( htree_t htree );
htree_t htree_insert( htree_t htree, htree_value_t val );
htree_value_t htree_pop( htree_t htree );


int main( void )
{
    htree_t htree = htree_create();
    
    for ( int i = 0; i < 20; i++ ) {
        int n = rand();
        htree_insert( htree, n );
        printf( "%8d\n", n );
    }
    printf( "========\n" );

    for ( int i = 0; i < 20; i++ ) {
        int n = htree_pop( htree );
        printf( "%8d\n", n );
    }
    
    htree_destroy( htree );
    
    return 0;
}

static int _cmp( const htree_value_t *a, const htree_value_t *b )
{
    if ( *a < *b ) return -1;
    if ( *a > *b ) return 1;
    return 0;
}


#define DEFAULT_HSIZE 16

htree_t htree_create()
{
    htree_t htree = malloc( sizeof( struct htree ) );
    if ( htree == NULL ) return NULL;
    htree->data    = malloc( sizeof( htree_value_t ) * DEFAULT_HSIZE );
    htree->n       = 0;
    htree->alloced = DEFAULT_HSIZE;
    return htree;
}

void htree_destroy( htree_t htree )
{
    if ( htree->data != NULL )
        free( htree->data );
    free( htree );
}

bool htree_isnull( htree_t htree )
{
    return htree == NULL;
}

static void _swap( htree_value_t *a, htree_value_t *b )
{
    htree_value_t tmp = *b;
    *b = *a;
    *a = tmp;
}

static htree_t _downheap( htree_t htree, int k, int n )
{
    htree_value_t *a   = htree->data;
    htree_cmp_t    cmp = _cmp;
    /* int j = k*2; */
    /* while ( j < n ) { */
        
    /* } */
    int j = k*2;
    while ( j+1 <= n ) {
        if ( cmp( &a[j-1], &a[j+1-1] ) < 0 ) j = j+1;
        if ( cmp( &a[k-1], &a[j-1] ) < 0 ) {
            _swap( &a[k-1], &a[j-1] );
            k = j;
            j = k*2;
        } else {
            break;
        }
    }
    
    if ( j == n ) {
        if ( cmp( &a[k-1], &a[j-1] ) < 0 ) {
            _swap( &a[k-1], &a[j-1] );
        }
    }
    return htree;
}

static htree_t _upheap( htree_t htree )
{
    htree_value_t *a   = htree->data;
    htree_cmp_t    cmp = _cmp;
    int n = htree->n;
    int j = n/2;
    while ( n > 1 ) {
        if ( cmp( &a[n-1], &a[j-1] ) > 0 ) {
            _swap( &a[n-1], &a[j-1] );
            n = j;
            j = n/2;
        } else {
            break;
        }
    }
    return htree;
}

htree_t htree_insert( htree_t htree, htree_value_t val )
{
    int n = htree->n;
    if ( htree->alloced <= n ) {
        htree_value_t *tmp = realloc( htree->data,
                                      sizeof( htree_value_t ) * htree->alloced*2 );
        if ( tmp == NULL ) return NULL;
        htree->alloced *= 2;
        htree->data     = tmp;
    }
    htree->data[n] = val;
    htree->n++;
    
    _upheap( htree );

    return htree;
}

htree_value_t htree_pop( htree_t htree )
{
    htree_value_t *a = htree->data;
    int n = htree->n;
    if ( htree->n > 1 ) {
        _swap( &a[0], &a[n-1] );
        _downheap( htree, 1, n-1 );
    }
    htree->n--;
    return a[n-1];
}