二叉堆应该是二叉树还是链表结构？

Question

我有一个任务要实现二叉堆。然而，我不确定是应该将二叉堆作为二叉树数据结构还是简单的双向链表来实现。

如果我应该将其实现为二叉树，那么如何跟踪树的最后一个元素以便插入新元素呢? 在链表中这将更容易。

所以，二叉堆一定要是二叉树吗？如果是，如何跟踪最后一个元素？

注意：在我的任务中有这样一句话： 但你将实现二叉堆不是作为数组，而是作为树。 为了更清晰，这是我的节点:

struct Word{
    char * word;
    int count;
    struct Word * parent;
    struct Word * left_child;
    struct Word * right_child;
}

- Yunus Eren Güzel

Answer 1

以下是问题中提供的解决方案。
作者：@Yunus Eren Güzel
已解决：

经过五个小时的研究，我找到了一种将堆实现为基于指针的树的方法。 插入算法如下：

insert
    node = create_a_node
    parent = get_the_last_parent
    node->parent = parent
    if parent->left==NULL
        parent->left=node
    else
        parent->right=node
end insert

get_last_parent parent,&height
    height++
    if parent->left==NULL || parent->right==NULL
        return parent;
    else
        int left_height=0,right_height=0;
        left = get_last_parent(parent->left,&left_height)
        right = get_last_parent(parent->right,&right_height)
        if left_height == right_height
            height += right_height
            return right
        else if left_height > right_height
            height += left_height
            return left
end get_last_parent

- bummi

---

这是什么语言？ - Gabriel Staples

Answer 2

一个二叉堆，根据定义，是一棵二叉树。在C语言中实现的一种方法是将树元素存储在数组中，其中数组索引对应于树元素（将根节点编号为0，其左子节点为1，其右子节点为2，依此类推）。然后，只需存储堆的大小（创建时初始化为0，并在添加元素时递增），并使用它来查找下一个空位置。

对于像这样的基本数据结构问题，维基百科是您的好帮手。

- jonmorgan

---

谢谢，但是这个任务有这样的陈述：“但你将实现二叉堆不作为一个数组，而是作为一棵树。” - Yunus Eren Güzel

Answer 3

你应该将它实现为一棵树。这样会很容易且有趣。如果是最大堆，堆只有一个属性，即任何节点的值都小于或等于其父节点。

在数组实现中，我们还要强加一些条件。如果你需要关于特定函数实现的帮助，可以随时问。

你需要向下遍历以添加新节点。

使用根节点和要插入的值来调用它。

    insert(node, x){

    if(node->value >= x)
      //insert
      if(node->left == 0)
          node->left = new Node(x);
      else if(node->right == 0)
          node->right = new Node(x);
      else if(node->left->value >= x)
         insert(node->left, x);
      else if(node->right->value >= x)
         insert(node->right, x);
      else
         //insert between node and its any one child
         insertBW(node, node->left, x);
   else  //if x is less than node value
      //insert between node and its parent
      insertBW(node->parent, node, x)
   }

insertBW(p, c) 是一个函数，它将一个包含值 x 的节点插入到 p 和 c 之间。

（我没有测试过这段代码，请检查是否有错误）

insertBW(Node* p, Node* c, T x)
{
    Node* newnode = new Node(x);
    newNode.x = x;
    if(p == 0)  //if node c is root
    {
       newnode.left = Tree.root.left;
       Tree.root = newnode;
    }
    else
    {
       newnode.parent = p;
       newnode.child  = c;
       if(p.left == c)
       {
           p.left = newnode;
       }
       else p.right = newnode;
    }
}

- Deepak

---

如果您告诉我如何跟踪最后一个元素，以便在插入新节点时使用，如果您能将其作为算法提供给我，那将非常有用。 - Yunus Eren Güzel

感谢您的努力，但我有疑问。insertBW是否会调用heapify？如果不是，它将破坏数据结构。您能给我提供insertBW算法吗？ - Yunus Eren Güzel

我看到你没有考虑将堆结构保持为完全二叉树。你的解决方案不是针对堆，而是针对自由形式的二叉树。 - Yunus Eren Güzel

条件 >= 使其成为堆。 - Deepak

Answer 4

对我来说，这似乎是一道作业题，看起来你在提问之前没有做过任何研究（抱歉用词有点严厉）:)

在计算机科学中，堆是一种专门的基于树的数据结构，满足堆属性：如果B是A的子节点，则key(A) ≥ key(B)。

我认为你的老师想让你实现一个优先队列数据结构，这就是你在同一个问题中同时谈到链表和堆的原因。优先队列可以作为堆或链表实现，在基于优先级提取元素时，你必须维护排序后的元素，例如在链表中，最大或最小的元素根据你是实现最大堆还是最小堆而放在前面，或者优先队列可以简单地实现为堆数据结构。

最后，你所说的“但你将实现二叉堆不是作为数组，而是作为树”，似乎与问题无关。请再次检查要求或重述分配给你的确切问题。

- Yavar

---

我已经研究了二叉堆实现作为二叉堆结构，但是我没有找到任何有用的资源。我认为问题很清楚，告诉我你不理解什么，我会进行修订。 - Yunus Eren Güzel

Answer 5

简单来说，关于你的第一个问题 - 不是。堆可以是任何东西（数组，链表，树，当必须即兴创作一群蓬松小猫时）。请注意堆的定义：如果“B”是“A”的子节点，则val（A）> = val（B）（或者在min-heap的情况下，val（A）<= val（B））。 最常见的是将其称为树（并且也将其实现为树），因为很容易将其视为树。此外，时间复杂度和性能都很好。

关于你的第二个问题，你没有提供任何信息，所以据我所知，搜索每个节点的解决方案与其他任何解决方案一样好... 要得到更好的答案，需要更多的信息（您有哪些限制，应支持哪些操作等）。

- Neowizard

Answer 6

一个二叉堆可以是任何东西，例如数组、链表、树等等。我们只需要保持正确的算法来访问数据。例如，如果您想将其设为左子项，则可以通过2N + 1（对于起始索引为0）来执行，其中N为父索引；或通过2N + 2将其设置为右子项。对于最后一个元素，您可以使用变量计数初始化堆，并在每次插入新元素时将其增加1，这样您就可以跟踪最后一个元素（删除同样道理，只需对集合进行一些修改）。

- Shravel Sharma