是否有可能进行有效的基于指针的二进制堆实现?

甚至可以使用指针而不是数组来实现二进制堆 ? 我搜索了互联网(包括SO),但没有找到答案。

这里的主要问题是,你如何跟踪最后一个指针? 将X插入堆中时,将X放在最后一个指针处,然后将其冒泡。 现在,最后一个指针指向哪里?

而且,当你想删除root时会发生什么? 您将根与最后一个元素交换,然后向下冒泡新根。 现在,您如何知道再次删除root时所需的新“最后一个元素”是什么?

解决方案1:维护指向最后一个节点的指针

在这种方法中,保持指向最后一个节点的指针,并且需要父指针。

  • 插入时,从最后一个节点开始导航到将插入新的最后一个节点的节点。 插入新节点并将其记住为最后一个节点。 根据需要将其向上移动。

  • 删除时,从最后一个节点开始导航到倒数第二个节点。 删除原始的最后一个节点,并记住刚找到的新的最后一个节点。 将原始最后一个节点移动到已删除节点的位置,然后根据需要在堆中向上或向下移动它。

可以在O(log(n))时间和O(1)空间中导航到所提到的节点。 以下是算法的说明,但代码如下:

  • 对于insert:如果最后一个节点是左子节点,则继续将新节点作为父节点的右子节点插入。 否则……从最后一个节点开始。 只要当前节点是正确的子节点,就向上移动。 如果未到达根,则移动到右侧的兄弟节点(必然存在)。 然后(无论是否到达根),尽可能向下移动到左侧。 继续插入新节点作为当前节点的左子节点。

  • 对于remove:如果最后一个节点是root,则继续删除root。 否则……从最后一个节点开始。 只要当前节点是左子节点,就向上移动。 如果未到达根,则移动到兄弟节点左侧节点(必然存在)。 然后(无论是否到达根),尽可能向下移动到右侧。 我们到达倒数第二个节点。

但是,有一些事情需要注意:

  • 删除时,有两种特殊情况:当删除最后一个节点时(取消链接节点并更改最后一个节点指针),以及何时删除倒数第二个节点(不是很特殊,但必须考虑这种可能性)用最后一个节点替换删除的节点时)。

  • 在向上或向下移动节点时,如果移动影响最后一个节点,则必须更正最后一个节点指针。

很久以前我已经实现了这一点。 万一它可以帮助某人, 这里是代码 。 在算法上它应该是正确的(也经过了validation的压力测试),但当然没有保证。

解决方案2:从根目录到达最后一个节点

此解决方案需要维护节点计数(但不是父指针或最后一个节点)。 通过从根向其导航找到最后一个(或倒数第二个)节点。

根据二进制堆的典型表示法,假设节点从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将在最坏的情况下向上遍历树的整个高度然后向下。

解决方案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)移动到被删除节点所持有的位置。 两者都只通过调整与其他节点之间的链接来工作,没有涉及的实际数据移动。 这些function应该不难实现,并且所提到的链接包括我的实现。

与基于arrays的实现相比,基于指针的二进制堆实现非常困难。 但编码它很有趣。 基本思想是二叉树。 但是你面临的最大挑战是让它保持不变。 您将难以找到必须插入节点的位置的确切位置。

为此,您必须知道二进制遍历。 我们做的是。 假设我们的堆大小是6.我们将数字+ 1,并将其转换为位。 7的二进制表示是“111”。 现在,记住要总是省略第一位。 所以,现在我们留下了“11”。 从左到右阅读。 该位为’1’,因此,转到根节点的右子节点。 然后左边的字符串是“1”,第一个比特是’1’。 由于您只剩下1位,这一位会告诉您插入新节点的位置。 因为它是’1’,所以新节点必须是当前节点的正确子节点。 因此,该过程的原始工作是将堆的大小转换为位。 省略第一位。 根据最左边的位,如果它是’1’,则转到当前节点的右子节点,如果它是’0’,则转到当前节点的左子节点。

插入新节点后,您将在堆中冒泡。 这告诉您将需要父指针。 所以,你一次走到树下,一次走到树上。 因此,您的插入操作将采用O(log N)。

至于删除,找到最后一个节点仍然是一个挑战。 我希望你熟悉堆中的删除,我们将它与最后一个节点交换并进行堆积。 但是为此您需要最后一个节点,为此,我们使用与查找插入新节点的位置相同的技术,但稍微扭曲一下。 如果要查找最后一个节点的位置,则必须使用值HeapSize本身的二进制表示forms,而不是HeapSize + 1.这将带您到最后一个节点。 因此,删除也会花费你O(log N)。

我在这里发布源代码时遇到了麻烦,但您可以参考我的博客中的源代码。 在代码中,也有Heap Sort。 这很简单。 我们只是继续删除根节点。 请参阅我的博客以获得有关数据的说明。 但我想这种解释会有所作为。

我希望我的回答对你有帮助。 如果有,请告诉我……! ☺

二进制堆是服从堆属性的完整二叉树。 就这样。 可以使用数组存储的事实非常方便。 但可以肯定的是,您可以使用链接结构来实现它。 这是一个有趣的运动! 因此,它主要用作练习或更高级的数据结构(例如,可用的,可寻址的优先级队列),因为它比执行arrays版本涉及更多。 例如,考虑一下siftup / siftdown程序,以及你需要做的所有边缘切割/缝纫。 无论如何,这不是太难,再一次,好玩!

对于那些说这是无用的练习的人来说,有一些(不可否​​认的)罕见的用例,其中基于指针的解决方案更好。 如果堆的最大大小未知,则arrays实现将需要在arrays填充时停止并复制到新存储中。 在存在固定响应时间约束和/或存在空闲存储器但不是足够大的连续块的系统(例如,嵌入式)中,这可能是不可接受的。 指针树允许您以小的固定大小的块递增分配,因此它没有这些问题。

为了回答OP的问题,不需要父指针和/或精细跟踪来确定插入下一个节点的位置或找到当前的最后一个节点。 您只需要堆大小的二进制rep中的位来确定要遵循的左右子指针。

编辑刚看到Vamsi Sangam @对此算法的解释。 尽管如此,这是代码中的演示:

 #include  #include  typedef struct node_s { struct node_s *lft, *rgt; int data; } NODE; typedef struct heap_s { NODE *root; size_t size; } HEAP; // Add a new node at the last position of a complete binary tree. void add(HEAP *heap, NODE *node) { size_t mask = 0; size_t size = ++heap->size; // Initialize the mask to the high-order 1 of the size. for (size_t x = size; x; x &= x - 1) mask = x; NODE **pp = &heap->root; // Advance pp right or left depending on size bits. while (mask >>= 1) pp = (size & mask) ? &(*pp)->rgt : &(*pp)->lft; *pp = node; } void print(NODE *p, int indent) { if (!p) return; for (int i = 0; i < indent; i++) printf(" "); printf("%d\n", p->data); print(p->lft, indent + 1); print(p->rgt, indent + 1); } int main(void) { HEAP h[1] = { NULL, 0 }; for (int i = 0; i < 16; i++) { NODE *p = malloc(sizeof *p); p->lft = p->rgt = NULL; p->data = i; add(h, p); } print(h->root, 0); } 

正如您所希望的那样,它会打印:

 0 1 3 7 15 8 4 9 10 2 5 11 12 6 13 14 

筛选可以使用相同类型的迭代。 也可以使用递归或显式堆栈来实现没有父指针的筛选,以“保存”从根到要筛选的节点的路径中的节点。

有许多注释指出,通过严格的定义,可以将二进制堆实现为树,并仍然将其称为二进制堆。

这是问题 – 没有理由这样做,因为使用数组在各方面都更好

如果你进行搜索以试图找到有关如何使用指针处理堆的信息,那么你将找不到任何东西 – 没有人会烦恼,因为没有理由以这种方式实现二进制堆。

如果你在树上搜索,你会发现很多有用的材料。 这是我最初的答案。 没有什么可以阻止人们这样做,但没有理由这样做。

你说 – 我必须这样做,我有一个遗留系统,我有指向我需要将它们放在堆中的节点。

创建这些指针的数组并在这个数组中使用它们,就像你需要内容取消引用它们时一样,使用基于标准数组的堆。 这比任何其他实现系统的方式都要好。

我认为没有其他理由使用指针实现堆。


原答案:

如果用指针实现它,那么它就是一棵树。 堆是一个堆,因为您可以如何计算子项的位置作为数组中的位置(2 *节点索引+1和2 *节点索引+ 2)。

所以不,你不能用指针实现它,如果你已经实现了一个树。

如果你搜索你会找到你的答案,那么实施树木就会有很好的记录。

我搜索了互联网(包括SO),但没有找到答案。

有趣,因为我在谷歌搜索的时候找到了答案 。 (同样的谷歌搜索引领我到这里。)

基本上:

  • 该节点应该有指向其父节点,左子节点和右子节点的指针。
  • 你需要保持指向:
    • 树的根( root )(duh)
    • 插入的最后一个节点( lastNode
    • 最低级别的最左边节点( leftmostNode
    • 下一个到最低级别的最右边节点( rightmostNode

现在,让要插入的节点是nodeToInsert 。 伪代码中的插入算法:

 void insertNode(Data data) { Node* parentNode, nodeToInsert = new Node(data); if(root == NULL) { // empty tree parent = NULL; root = nodeToInsert; leftmostNode = root; rightmostNode = NULL; } else if(lastNode.parent == rightmostNode && lastNode.isRightChild()) { // level full parentNode = leftmostNode; leftmostNode = nodeToInsert; parentNode->leftChild = nodeToInsert; rightmostNode = lastNode; } else if (lastNode.isLeftChild()) { parentNode = lastNode->parent; parentNode->rightChild = nodeToInsert; } else if(lastNode.isRightChild()) { parentNode = lastNode->parent->parent->rightChild; parentNode->leftChild = nodeToInsert; } nodeToInsert->parent = parentNode; lastNode = nodeToInsert; heapifyUp(nodeToInsert); } 

删除伪代码:

 Data deleteNode() { Data result = root->data; if(root == NULL) throw new EmptyHeapException(); if(lastNode == root) { // the root is the only node free(root); root = NULL; } else { Node* newRoot = lastNode; if(lastNode == leftmostNode) { newRoot->parent->leftChild = NULL; lastNode = rightmostNode; rightmostNode = rightmostNode->parent; } else if(lastNode.isRightChild()) { newRoot->parent->rightChild = NULL; lastNode = newRoot->parent->leftChild; } else if(lastNode.isLeftChild()) { newRoot->parent->leftChild = NULL; lastNode = newRoot->parent->parent->leftChild->rightChild; } newRoot->leftChild = root->leftChild; newRoot->rightChild = root->rightChild; newRoot->parent = NULL; free(root); root = newRoot; heapifyDown(root); } return result; } 

heapifyUp()heapifyDown()不应该太难,但当然你必须确保这些函数不会使lastNoderightmostNodelastNode指向错误的位置。

TL; DR只需使用该死的arrays。