1

可能重复：
斜堆的 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;
    }
}

我的问题是我不知道如何从这个倾斜堆中正确插入和删除结构。提前致谢。

4

1 回答 1

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

于 2012-11-13T04:19:57.073 回答