使用倾斜堆来保存 C 中的结构

Question

可能的重复项：
C 倾斜堆的实现

我有以下结构：

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直接存储在堆中的每个节点中，不如存储指向任务的指针。插入方法应采用指向要添加的任务的指针。它将需要为节点中的任务分配内存，然后将相关数据复制到其中。您需要在删除方法中释放它。

例如

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 和一个浮点数，所以复制它不是很昂贵，但更一般地说，你应该使用指向任务的指针。在您的情况下，存储实际结构而不是指向结构的指针也会浪费更多内存，因为每个节点中都有一个显式根指针。我强烈建议无论如何都摆脱它（它既不优雅又完全没有必要），但这需要重写相当多的代码。