C：バイナリヒープの最小要素を削除する

Question

私はバイナリヒープのC実装で作業しています。最小の要素はツリーの基底にあり、最大のものではありません。そして、木の次の各要素は前の要素よりも大きくなります。

私の問題は、ヒープの最小要素を削除するときです。バイナリヒープを定義し、初期化し、最小要素を削除するためのコードです。

struct BinaryHeap 
{ 
    int capacity; 
    int size; 
    int *heap; 
}; 

void init_heap(struct BinaryHeap *heap_ptr, int capacity) 
{ 
    heap_ptr->capacity = capacity; 
    heap_ptr->size = 0; 
    double n = ceil(pow(2, log10(capacity)/log10(2))); 
    heap_ptr->heap = (int *)malloc(n*sizeof(int)); 
} 

int remove_heap(struct BinaryHeap *heap_ptr) 
{ 
    if (heap_ptr->size > 0) 
    { 
     int min_item = heap_ptr->heap[1]; 
     heap_ptr->heap[1] = heap_ptr->heap[heap_ptr->size]; 

     heap_ptr->size--; 
     heap_ptr->heap[1] = NULL; // I get a warning here 

     if (heap_ptr->size > 0) 
     { 
      heapify(heap_ptr, 1); // helper function which percolates the heap after removal 
     } 
     return min_item; 
    } 
    return 0; 
} 

Answer 1

NULLは整数値ではなく、NULLポインタ用です。あなたは他の達成不可能な値に設定する必要があります。たとえば、ヒープ内にゼロまたは正の数しか指定できない場合は、負の値に設定できます。

値が整数の範囲全体に及ぶ場合は、未使用のエントリを追跡する他の方法が必要です。たとえば、heapの対応する値が有効であるかどうかを示すブーリアンフラグを含む第2の配列を持つことによって実現される。