Der*_*ang 8 c c++ algorithm binary-tree pointers
甚至可以使用指针而不是数组来实现二进制堆？我搜索了互联网(包括SO),但没有找到答案.
这里的主要问题是,如何跟踪最后一个指针？当您将X插入堆中时,将X放在最后一个指针处,然后将其冒泡.现在,最后一个指针指向哪里？
而且,当您想要删除根时会发生什么？您将根与最后一个元素交换,然后向下冒泡新根.现在,您如何知道再次删除root时所需的新"最后一个元素"是什么？
Amb*_*jak 10
在这种方法中,保持指向最后一个节点的指针,并且需要父指针.
插入时,从最后一个节点开始导航到将插入新的最后一个节点的节点.插入新节点并将其记住为最后一个节点.根据需要将其向上移动.
删除时,从最后一个节点开始导航到倒数第二个节点.删除原始的最后一个节点,并记住刚刚找到的新的最后一个节点.将原始最后一个节点移动到已删除节点的位置,然后根据需要在堆中向上或向下移动它.
可以在O(log(n))时间和O(1)空间中导航到所提到的节点.以下是算法的说明,但代码如下:
对于insert:如果最后一个节点是左子节点,则继续将新节点作为父节点的右子节点插入.否则......从最后一个节点开始.只要当前节点是正确的子节点,就向上移动.如果未到达根,则移动到右侧的兄弟节点(必然存在).然后(无论是否到达根),尽可能向下移动到左侧.继续插入新节点作为当前节点的左子节点.
对于remove:如果最后一个节点是root,则继续删除root.否则......从最后一个节点开始.只要当前节点是左子节点,就向上移动.如果未到达根,则移动到兄弟节点左侧节点(必然存在).然后(无论是否到达根),尽可能向下移动到右侧.我们到达倒数第二个节点.
但是,有一些事情需要注意:
删除时,有两种特殊情况:当删除最后一个节点时(取消链接节点并更改最后一个节点指针),以及何时删除倒数第二个节点(不是很特殊,但必须考虑这种可能性)用最后一个节点替换删除的节点时).
在堆中向上或向下移动节点时,如果移动影响最后一个节点,则必须更正最后一个节点指针.
很久以前我已经实现了这一点.万一它可以帮助某人,这里是代码.在算法上它应该是正确的(也经过了验证的压力测试),但当然没有保证.
此解决方案需要维护节点计数(但不是父指针或最后一个节点).通过从根向其导航找到最后一个(或倒数第二个)节点.
假设节点从1开始编号,根据二进制堆的典型符号.选择任何有效的节点号并以二进制表示.忽略第一个(最重要的)1位.其余位定义从根到该节点的路径; 零表示左,一表示右.
例如,要到达节点11(= 1011b),从根开始然后向左(0),向右(1),向右(1).
此算法可用于插入以查找新节点的放置位置(遵循节点node_count + 1的路径),并在remove中找到倒数第二个节点(遵循节点node_count-1的路径).
这种方法在libuv中用于定时器管理; 看看他们实现的二进制堆.
这里的许多答案甚至文献都说基于数组的二进制堆实现是非常优越的.但是我对此提出质疑,因为有些情况下不希望使用数组,通常是因为数组的大小不是预先知道的,并且数组的按需重新分配不被认为是可接受的,例如由于延迟或可能性分配失败.
libuv(一个广泛使用的事件循环库)使用带指针的二进制堆的事实进一步说明了这一点.
值得注意的是,Linux内核在少数情况下使用(基于指针的)红黑树作为优先级队列,例如用于CPU调度和定时器管理(与libuv中的目的相同).我发现更改这些以使用基于指针的二进制堆可能会提高性能.
可以将解决方案1和解决方案2组合成混合方法,该方法动态选择任一算法(用于查找最后或倒数第二个节点),具有较低成本的算法,以需要的边数来衡量被遍历.假设我们想要导航到节点号N,并且highest_bit(X)意味着N中最高位的0的索引(0表示LSB).
从根导航的成本(解决方案2)是highest_bit(N).
从同一级别的前一节点导航的成本(解决方案1)是:2 * (1 + highest_bit((N-1) xor N)).
请注意,在级别更改的情况下,第二个等式将产生错误(太大)的结果,但是在这种情况下,从根开始遍历更有效(估计是正确的)并且将被选择,因此存在无需特殊处理.
一些CPU具有highest_bit允许非常有效地实现这些估计的指令.另一种方法是将最高位保持为位掩码,并使用位掩码而不是位索引进行这些计算.例如,考虑1后跟N个零平方等于1,后跟2N个零).
在我的测试中,事实证明解决方案1平均比解决方案2更快,并且混合方法似乎具有与解决方案2大致相同的平均性能.因此,混合方法仅在需要最小化最坏情况时才有用.时间,这在解决方案2中是(两次)更好; 因为解决方案1将在最坏的情况下遍历树的整个高度然后向下.
请注意,插入中的遍历代码与上述算法略有不同,但仍然正确.
struct Node {
Node *parent;
Node *link[2];
};
struct Heap {
Node *root;
Node *last;
};
void init (Heap *h)
{
h->root = NULL;
h->last = NULL;
}
void insert (Heap *h, Node *node)
{
// If the heap is empty, insert root node.
if (h->root == NULL) {
h->root = node;
h->last = node;
node->parent = NULL;
node->link[0] = NULL;
node->link[1] = NULL;
return;
}
// We will be finding the node to insert below.
// Start with the current last node and move up as long as the
// parent exists and the current node is its right child.
Node *cur = h->last;
while (cur->parent != NULL && cur == cur->parent->link[1]) {
cur = cur->parent;
}
if (cur->parent != NULL) {
if (cur->parent->link[1] != NULL) {
// The parent has a right child. Attach the new node to
// the leftmost node of the parent's right subtree.
cur = cur->parent->link[1];
while (cur->link[0] != NULL) {
cur = cur->link[0];
}
} else {
// The parent has no right child. This can only happen when
// the last node is a right child. The new node can become
// the right child.
cur = cur->parent;
}
} else {
// We have reached the root. The new node will be at a new level,
// the left child of the current leftmost node.
while (cur->link[0] != NULL) {
cur = cur->link[0];
}
}
// This is the node below which we will insert. It has either no
// children or only a left child.
assert(cur->link[1] == NULL);
// Insert the new node, which becomes the new last node.
h->last = node;
cur->link[cur->link[0] != NULL] = node;
node->parent = cur;
node->link[0] = NULL;
node->link[1] = NULL;
// Restore the heap property.
while (node->parent != NULL && value(node->parent) > value(node)) {
move_one_up(h, node);
}
}
void remove (Heap *h, Node *node)
{
// If this is the only node left, remove it.
if (node->parent == NULL && node->link[0] == NULL && node->link[1] == NULL) {
h->root = NULL;
h->last = NULL;
return;
}
// Locate the node before the last node.
Node *cur = h->last;
while (cur->parent != NULL && cur == cur->parent->link[0]) {
cur = cur->parent;
}
if (cur->parent != NULL) {
assert(cur->parent->link[0] != NULL);
cur = cur->parent->link[0];
}
while (cur->link[1] != NULL) {
cur = cur->link[1];
}
// Disconnect the last node.
assert(h->last->parent != NULL);
h->last->parent->link[h->last == h->last->parent->link[1]] = NULL;
if (node == h->last) {
// Deleting last, set new last.
h->last = cur;
} else {
// Not deleting last, move last to node's place.
Node *srcnode = h->last;
replace_node(h, node, srcnode);
// Set new last unless node=cur; in this case it stays the same.
if (node != cur) {
h->last = cur;
}
// Restore the heap property.
if (srcnode->parent != NULL && value(srcnode) < value(srcnode->parent)) {
do {
move_one_up(h, srcnode);
} while (srcnode->parent != NULL && value(srcnode) < value(srcnode->parent));
} else {
while (srcnode->link[0] != NULL || srcnode->link[1] != NULL) {
bool side = srcnode->link[1] != NULL && value(srcnode->link[0]) >= value(srcnode->link[1]);
if (value(srcnode) > value(srcnode->link[side])) {
move_one_up(h, srcnode->link[side]);
} else {
break;
}
}
}
}
}
使用另外两个函数:move_one_up将节点在堆中向上移动一步,并replace_node替换将现有节点(srcnode)移动到被删除节点所持有的位置.两者都只通过调整与其他节点之间的链接来工作,没有涉及的实际数据移动.这些功能应该不难实现,并且所提到的链接包括我的实现.
有许多评论指出，通过严格的定义，可以将二叉堆实现为树，但仍将其称为二叉堆。
问题是——没有理由这样做，因为使用数组在各方面都更好。
如果您进行搜索以尝试查找有关如何使用指针使用堆的信息，您将找不到任何信息——没有人会打扰，因为没有理由以这种方式实现二进制堆。
如果您在树木上进行搜索，您会发现很多有用的材料。这就是我原来回答的重点。没有什么可以阻止人们这样做，但从来没有理由这样做。
你说——我必须这样做，我有一个遗留系统，我有指向节点的指针，我需要将它们放入堆中。
创建这些指针的数组，并在需要内容取消引用它们时，像使用基于标准数组的堆一样在该数组中使用它们。这将比任何其他实现系统的方法效果更好。
我想不出使用指针实现堆的其他原因。
原答案：
如果你用指针实现它，那么它就是一棵树。堆之所以是堆，是因为您可以将子级的位置计算为数组中的位置（2 * 节点索引 +1 和 2 * 节点索引 + 2）。
所以不，你不能用指针来实现它，如果你这样做，你已经实现了一棵树。
实现树有详细的文档记录，如果您搜索，您会找到答案。