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

Question

我有一个实现二进制堆的作业。但是，我不确定是否应该将二叉堆实现为二叉树数据结构或简单的双链表。

如果我应该实现为二叉树，我应该如何跟踪树的最后一个元素以便插入新元素？在链表中，这会容易得多。

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

注意：在我的作业中有这样一句话： 但是你不会将二叉堆实现为数组，而是 作为一棵树。

更清楚地说，这是我的节点：

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

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

Answer 2

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

对于像这样的基本数据结构问题，维基百科是你的朋友。

Answer 3

您应该将其实现为一棵树。这将是简单而有趣的。堆的唯一属性是，如果它是最大堆，则任何节点的值都小于或等于其父节点。
在数组实现中，我们施加了更多条件。
如果您需要有关具体功能实现的帮助，可以询问。

您需要向下移动以添加新节点

，用 root 调用它，要插入的值

    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) 是一个函数，它在 p 和 c 之间插入包含值 x 的节点

（我没有测试此代码，请检查错误）

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;
    }
}

Answer 4

对我来说，这确实是一个家庭作业问题。看来你在提问之前没有自己做过任何研发（对不起，有点刺耳的话）:)

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

我认为你的老师希望你实现一个优先级队列数据结构，这就是你在同一问题中同时讨论链表和堆的地方。优先级队列可以实现为堆或链表，其中根据优先级提取元素，您必须在链表的情况下维护已排序的元素，其中最大或最小元素位于前面，具体取决于您是否正在实现最大堆或最小堆或优先级队列可以简单地实现为堆数据结构。

来到最后一点，您说“但是您将不是将二进制堆实现为数组，而是实现为树。”似乎非常无关紧要。请再次检查所需内容或重现作业中提出的确切问题。

Answer 5

简而言之，关于你的第一个问题——不。堆可以是任何东西（数组、链表、树，以及当一个人必须临时搭建一个毛茸茸的小猫家族时）。请注意堆的定义：如果“B”是“A”的子级，则 val(A) >= val(B) （或者，在最小堆的情况下，val(A) <= val( B））。
最常见的是将其称为树（也可以这样实现），因为很容易将其视为一棵树。此外，时间复杂度和性能都不错。

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

Answer 6

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