c++ - 查找链接结构堆中的最后一个元素

Question

我想知道您将如何在堆和根元素的链接结构实现中找到最远的元素。我希望能够 Enque 和 Deque 元素。

一些澄清：我的意思是说你有一个链接结构组成一个最大堆（根元素具有最大值）。您的树将在最底部的某处有一个元素，您可以在之后插入或删除，具体取决于您是入队还是出队。你如何确定那个元素？以及如何确定树的根节点？（上一个）

Answer 1

我并不完全肯定这是您所要求的，但这是指向单链表最后一个元素的一种方式：

T *p = NULL, *q = NULL;  // q follows p by one node
p = root;
while (p)
{
    q = p;
    p = p -> next;
}

// q now points to last node

Answer 2

向堆结构中添加内容的常规方法是从根开始并“遍历”树以找到新元素所在的位置。当你找到它去哪里时，你把它放在那里，如果这意味着替换那个地方已经存在的东西，那么你就取之前的值并继续往下走去寻找它去哪里。重复直到你碰到一片叶子，然后添加你“携带”的任何值作为该叶子的适当子级。

假设你的新值是 5，堆的根节点是 10。5 显然低于 10，所以你看看 10 的孩子。假设它们是 8 和 7。两者都大于 5，所以选择一个（你如何选择一个取决于你是否试图保持堆平衡）。假设你选择 7，它有孩子 3 和 4。5 低于 7，但高于 3 或 4，所以你用 5 替换 4，然后查看该节点的孩子，看看将 4 放在哪里。假设它没有孩子，你可以添加一个包含 4 的新叶子。

至于您关于如何找到根的问题——通常根是指向您保留的树的唯一指针。这是您所有操作的起点。如果您从其他地方开始，我想您可以导航到根目录，但我会质疑为什么。

Answer 3

也许是这样的？

struct node {
  node *parent;
  node *children[2];
  int data; //or whatever else you want
};

struct heap {
  node *root;
  node *last;
};

这比仅使用数组实现起来要复杂得多。这是一个假设的添加

void add(struct heap* h, int d)
{
  node* add = malloc(sizeof(node));
  add->data = d;
  node* current = h->root;
  while(current->children[1]) current = current->children[1];
  current->children[1] = add;
  add.parent = current;
  add.children[0] = NULL;
  add.children[1] = NULL; 
  h.last = add;
  percolate_up(h);
}

类似的东西。