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用於空指針，不用於整數值。您需要將其設置爲其他無法實現的值。例如，如果堆中只能有零個或正數，則可以將其設置爲負值。

如果您的值可以涵蓋整個整數範圍，那麼您需要一些其他方式來跟蹤未使用的條目。例如通過讓第二個數組包含一個布爾標誌來說明heap中的對應值是否有效。