Binary Heap是二叉树还是链表？

我有一个任务来实现一个二进制堆。但是，我不确定是否应该将二进制堆实现为二叉树数据结构或简单的双链表。Binary Heap是二叉树还是链表？

如果我应该实现一个二叉树，我应该如何跟踪树的最后一个元素以插入一个新元素？在链接列表，会更容易。

那么，二进制堆是否必须是二叉树？如果是的话，如何追踪最后的元素？

注：我的任务有这样的语句： 但你将实现二元堆而不是作为一个阵列，但一棵树。

更清楚，这是我的节点：

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

来源

2012-02-18 Yunus Eren Güzel

从问题的解决方案。
通过@Yunus二连居泽尔
解决：

后五小时的学习我已经找到一种方法来实现堆为指针基于树。插入算法是：

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

来源

2015-02-08 20:28:58 bummi

这是什么语言？ – 2017-08-06 02:02:41

二元堆，顾名思义，二叉树。在C中实现这一点的一种方式是将树元素存储在其中数组索引对应于树元素（编号根节点0，其左子元素1，右子元素2等）的数组中。然后，您可以只存储堆的大小（创建时初始化为0，每当添加一个元素时都会增加）并使用它来查找下一个打开的位置。

对于这样的基本数据结构问题，Wikipedia is your friend。

来源

2012-02-18 17:01:25 jonmorgan

感谢，但分配有这种说法：“但你不会实现二叉堆作为一个数组，但一棵树” – 2012-02-18 17:08:46

你应该把它作为一个树来实现。这将是容易和有趣的。堆只具有任何节点的值小于或等于其父值的属性，如果它是最大堆。在数组实现中，我们施加了更多条件。如果您需要关于特定功能实现的帮助，那么您可以问问它。

您需要向下行进到添加新节点

与根调用它，值被插入

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

来源

2012-02-18 17:40:31 Deepak

如果您告诉我如何跟踪我插入新节点时将使用的最后一个元素，如果将它作为算法给出，对我而言将会非常有用。 – 2012-02-18 18:00:09

谢谢你的负担，但我在脑海中有疑问。 insertBW是否会进行heapify调用？如果不是，则会破坏数据结构。你能给我insertBW算法吗？ – 2012-02-18 18:31:43

我看到你没有想到将堆结构保留为一个二进制树。你的解决方案不是为了堆，而是为了自由形式的二叉树。 – 2012-02-18 22:43:51

这对我来说似乎真的是一门功课的问题&看来你没有做你自己的任何[R & d问（对不起，有点难听的话）之前:)

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

我认为你的老师希望你实现一个优先级队列数据结构，这就是你在同一个问题中谈论链接列表和堆在一起的地方。优先级队列可以实现为堆或链接列表，其中根据优先级提取元素，或者您必须在链接列表的情况下对元素进行排序，其中最大或最小元素根据您是否正在执行最大堆或最小堆OR优先级队列可以简单地实现为堆数据结构。

来到你说的最后一点“但是你将二进制堆不是作为一个数组，而是作为一个树来实现”，似乎是非常不相关的。请再次检查是否需要或重现您的任务中已提出的确切问题。

来源

2012-02-18 18:32:23 Yavar

我已经研究了Binary Heap实现作为二进制堆结构，但是我找不到任何有用的资源。我认为这个问题很明确，告诉我你不了解的内容，然后修改它。 – 2012-02-18 22:41:01

简而言之，关于你的第一个问题 - 不是。堆可以是任何东西（数组，链表，树，以及何时必须即兴蓬松的小猫家族）。请注意堆的定义：如果“B”是“A”的子元素，那么val（A）> = val（B）（或者在最小堆的情况下，val（A）< = val ）。最常见的是将其称为树（也是这样实现的），因为很容易将其视为树。此外，时间复杂性表现还是不错的。

关于你提到的第二个问题，你没有给出信息，所以据我知道，搜索每个节点的解决方案是任何其他好...
对于任何一个更好的答案，需要更多的信息（是什么做的限制你有什么操作，你应该支持，等等......）

来源

2012-02-19 17:52:48 Neowizard

Binary Heap是二叉树还是链表？

回答

相关问题