我有一个实现二进制堆的赋值。然而，我不确定我应该将二进制堆实现为二进制树数据结构还是简单的双链表。
如果我应该实现为一个二叉树，我应该如何跟踪树的最后一个元素以便插入一个新元素？在链接列表中，这会容易得多。
那么，二进制堆必须是一个二进制树吗？如果是，如何跟踪最后一个元素？
注意：在我的作业中有这样一句话：但是您将不将二进制堆实现为数组，而是作为一棵树
更清楚地说，这是我的节点：
struct Word{
char * word;
int count;
struct Word * parent;
struct Word * left_child;
struct Word * right_child;
}
问题的解决方案
作者：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
根据定义，二进制堆是一个二进制树。在C中实现这一点的一种方法是将树元素存储在数组中，其中数组索引对应于树元素（对根节点0、其左子节点1、其右子节点2进行编号，依此类推）。然后，您可以只存储堆的大小（在创建时初始化为0，并在添加元素时递增），然后使用它来查找下一个打开的位置。
对于像这样的基本数据结构问题，维基百科是你的朋友。
您应该将其实现为树。这将是简单而有趣的。堆只有一个属性，即任何节点的值都小于或等于其父节点（如果它是最大堆）。在数组实现中，我们施加了更多的条件。如果你需要关于具体功能实现的帮助，那么你可以问它
您需要向下移动以添加新节点
用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;
}
}
对我来说，这似乎真的是一个家庭作业问题&你似乎没有做任何R&D在你自己问之前（对不起有点刺耳的话）：）
在计算机科学中，堆是一种专门的基于树的数据结构，它满足堆的性质：如果B是a的子节点，则键（a）≥键（B）。
我想你的老师希望你实现一个优先级队列数据结构，这就是你在同一个问题中同时讨论链表和堆的地方。Priority Queue可以实现为Heap或Linked List，其中要根据优先级提取元素，您必须在链表的情况下对元素进行排序，其中最大或最小元素位于最前面，这取决于您是实现最大堆还是最小堆，或者优先级队列可以简单地实现为堆数据结构。
到了最后一点，你说"但是你将把二进制堆实现为一棵树，而不是一个数组"，这似乎无关紧要。请再次检查所需内容，或重复作业中提出的确切问题。
简单地说，关于你的第一个问题-否。堆可以是任何东西（数组、链表、树，以及当你必须即兴制作一个毛茸茸的小猫家族时）。注意堆的定义：如果"B"是"a"的子级，则val（a）>=val（B）（或者，在最小堆的情况下，val（a）<=val（B））。最常见的是将它称为树（也可以这样实现），因为很容易将其视为树。此外，时间复杂性&性能良好。
关于你的第二个问题，你没有提供任何信息，据我所知，搜索每个节点的解决方案和其他任何解决方案一样好
为了得到更好的答案，需要更多的信息（您有什么限制，应该支持什么操作等）
二进制堆可以是任何东西，例如数组、链表、树等。我们只需要保留正确的算法来访问数据。例如，如果您想到达左边的子级，您可以通过2N+1（对于起始索引0）来完成，其中N是父级索引或右边的子级通过2N+2。对于最后一个元素，您可以使用变量计数初始化堆，并在每次插入新元素时将其递增1，这样您就可以跟踪最后一个图元（与删除相同，只需对集合进行一些修改）。