heap.c

任意给定三维空间的点集

/*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 * heap.C -
 *     
\*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*/

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

#include  "heap.h"

/*--- Constants ---*/

/*--- Start of Code ---*/

void  heap_init( heap_t  * pHeap, ptrCompareFunc  _pCompFunc )
{
    assert( pHeap != NULL );
    assert( _pCompFunc != NULL );
    
    memset( pHeap, 0, sizeof( heap_t ) );

    pHeap->pCompFunc = _pCompFunc;
    pHeap->max_size = 100;
    pHeap->pArr = (voidPtr_t *)malloc( sizeof( void * ) 
                                       * pHeap->max_size );
    assert( pHeap->pArr != NULL );
    pHeap->curr_size = 0;
}


static void  resize( heap_t  * pHeap, int  size ) 
{
    int  max_sz;
    voidPtr_t  * pTmp;

    if   ( size <= pHeap->max_size ) 
        return;

    max_sz = size * 2;
    pTmp = (voidPtr_t *)malloc( max_sz * sizeof( void * ) );
    assert( pTmp != NULL );
    memset( pTmp, 0, max_sz * sizeof( void * ) );
    memcpy( pTmp, pHeap->pArr, pHeap->curr_size * sizeof( void * ) );
    free( pHeap->pArr );
    pHeap->pArr = pTmp;
}


void  heap_term( heap_t  * pHeap )
{
    assert( pHeap != NULL );

    if  ( pHeap->pArr != NULL ) 
        free( pHeap->pArr );
    memset( pHeap, 0, sizeof( heap_t ) );
}


void  heap_insert( heap_t  * pHeap, void  * pData )
{
    int  ind, father;
    voidPtr_t  pTmp;

    resize( pHeap, pHeap->curr_size + 1 );
    
    ind = pHeap->curr_size;
    pHeap->curr_size++;

    pHeap->pArr[ ind ] = pData;

    while  ( ind > 0 ) {
        father = ( ind - 1 ) / 2;
        
        if  ( (*pHeap->pCompFunc)( pHeap->pArr[ ind ], 
                                   pHeap->pArr[ father ] ) <= 0 )
            break;

        pTmp = pHeap->pArr[ ind ];
        pHeap->pArr[ ind ] = pHeap->pArr[ father ];
        pHeap->pArr[ father ] = pTmp;

        ind = father;
    }    
}


void  * heap_delete_max( heap_t  * pHeap )
{
    void  * res;
    void  * pTmp;
    int  ind, left, right, max_ind;

    if  ( pHeap->curr_size <= 0 )
        return  NULL;

    res = pHeap->pArr[ 0 ];

    pHeap->curr_size--;
    pHeap->pArr[ 0 ] = pHeap->pArr[ pHeap->curr_size ]; 
    ind = 0;

    while  ( ind < pHeap->curr_size ) {
        left = 2 * ind + 1;
        right = 2 * ind + 2;
        if  ( left >= pHeap->curr_size ) 
            break;
        if  ( right >= pHeap->curr_size ) 
            right = left;
        
        if  ( (*pHeap->pCompFunc)( pHeap->pArr[ left ], 
                                   pHeap->pArr[ right ] ) <= 0 )
            max_ind = right;
        else
            max_ind = left;
        if  ( (*pHeap->pCompFunc)( pHeap->pArr[ ind  ], 
                                   pHeap->pArr[ max_ind ] ) >= 0 )
            break;
        
        pTmp = pHeap->pArr[ ind ];
        pHeap->pArr[ ind ] = pHeap->pArr[ max_ind ];
        pHeap->pArr[ max_ind ] = pTmp;

        ind = max_ind;
    }

    return  res;
}


bool  heap_is_empty( heap_t  * pHeap )
{
    assert( pHeap != NULL );

    return( pHeap->curr_size <= 0 );
}


/* heap.C - End of File ----------------------------------------------------*/