使用斜堆在C持有結構

Question

可能重複：
C implementation of skew heap

我有以下結構：

typedef struct Task_t { 
    float length; 
    int value; 
} task_t; 

我試圖用一個歪斜堆使用'價值'來持有這些結構的一堆。所以具有最低「值」的結構將是根。我的傾斜堆實施如下：

typedef struct node 
{ 
int value; 
struct node * root; 
struct node * leftchild; 
struct node * rightchild; 
} Node; 

typedef Node * skewHeap; 

struct skewHeap 
{ 
    struct node * root; 
}; 
void skewHeapInit (struct skewHeap *sk) 
{ 
    sk->root = 0; 
} 
void skewHeapAdd (struct skewHeap *sk) 
{ 
    struct node *n = (struct node *) malloc(sizeof(struct node)); 
    struct node *s; 
    assert(n != 0); 
    n->value = 0; 
    n->leftchild = 0; 
    n->rightchild = 0; 
    s->root = skewHeapMerge(s->root,n); 
} 

void skewHeapRemoveFirst (struct skewHeap *sk) 
{ 
    struct node * n = sk->root; 
    sk->root = skewHeapMerge(n->leftchild, n->rightchild); 
    free(n); 

} 

struct node * skewHeapMerge(struct node *left, struct node *right) 
{ 

    struct node *temp; 

    if (left == NULL) 
     return right; 

    if (right == NULL) 
     return left; 

    if (left->value < right->value) 
    { 
     temp = left->leftchild; 
     left->leftchild = skewHeapMerge(left->rightchild, right); 
     left->rightchild = temp; 
     return left; 
    } 
    else 
    { 
     temp = right->rightchild; 
       right->rightchild = skewHeapMerge(right->leftchild, left); 
     right->leftchild = temp; 
     return right; 
    } 
} 

我的問題是我不知道如何正確插入和刪除這個歪斜堆的結構。提前致謝。

Answer 1

取而代之的是將value直接存儲在堆中的每個節點中，而不是將指針存儲到任務中。您的插入方法應該帶有一個指向您要添加的任務的指針。它需要爲節點中的任務分配內存，然後複製相關數據。您需要在清除方法中釋放此內存。

E.g.

typedef struct node 
{ 
    Task_t *task; 
    struct node *root; 
    struct node *left; 
    struct node *right; 
} Node; 

// your add should have passed in a value, because the only thing your code adds to the heap is zeros 
void skewHeapAdd (struct skewHeap *sk, Task_t *task); 

說實話，你可以只存儲Task_t task;而不是使用指針，因爲它只包含一個int和一個浮點所以複製不是很昂貴，但更普遍的，你應該使用一個指向一個任務。在你的情況下，通過存儲實際的結構而不是指向結構體的指針，你也會浪費更多的內存，因爲你在每個節點中都有一個明確的根指針。無論如何，我強烈建議不要這樣做（這不僅不夠好，而且完全沒有必要），但是這需要重寫相當一部分代碼。