C: Minimales Element eines Binären Heaps entfernen

Question

Ich arbeite an einer C-Implementierung eines binären Heaps, bei dem das kleinste Element an der Basis des Baums statt des größten Elementes liegt. Und dann ist jedes nächste Element im Baum größer als das vorherige.

Mein Problem ist, wenn ich das kleinste Element des Heap entfernen. Hier ist mein Code zum Definieren eines binären Heaps, Initialisieren eines und Entfernen des minimalen Elements.

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 ist für Null-Zeiger, nicht für ganzzahlige Werte. Sie müssen es auf einen anderen nicht erreichbaren Wert setzen. Wenn Sie beispielsweise nur Null oder positive Zahlen im Heapspeicher haben, können Sie einen negativen Wert festlegen.

Wenn Ihre Werte den gesamten Bereich von ganzen Zahlen umfassen können, benötigen Sie eine andere Möglichkeit, nicht verwendete Einträge zu verfolgen. zum Beispiel durch ein zweites Array, das ein boolesches Flag enthält, das angibt, ob der entsprechende Wert in heap gültig ist oder nicht.