10

甚至可以使用指针而不是数组来实现二进制堆吗？我在互联网上搜索过（包括 SO），但找不到答案。

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

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

4

6 回答 6

14

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

在这种方法中，指向最后一个节点的指针被维护，并且需要父指针。

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

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

可以在 O(log(n)) 时间和 O(1) 空间中导航到提到的节点。这是算法的描述，但代码如下：

  • 对于插入：如果最后一个节点是左子节点，则继续插入新节点作为父节点的右子节点。否则...从最后一个节点开始。只要当前节点是右孩子，就向上移动。如果未到达根，则移动到右侧的兄弟节点（必须存在）。然后（无论是否到达根），尽可能向左移动。继续插入新节点作为当前节点的左子节点。

  • 对于删除：如果最后一个节点是根，则继续删除根。否则...从最后一个节点开始。只要当前节点是左子节点，就向上移动。如果没有到达根，则移动到同级左节点（它必然存在）。然后（无论是否到达根），尽可能向右移动。我们已经到达倒数第二个节点。

但是，有一些事情需要注意：

  • 移除时，有两种特殊情况：移除最后一个节点时（取消链接节点并更改最后一个节点指针），以及移除倒数第二个节点时（不是很特别，但必须考虑可能）当用最后一个节点替换已删除的节点时）。

  • 当在堆中向上或向下移动节点时，如果移动影响到最后一个节点，则必须更正最后一个节点的指针。

很久以前，我已经实现了这一点。如果它对某人有帮助，这里是代码。算法上它应该是正确的（也经过了压力测试和验证），但当然没有保证。

解决方案2：从根到达最后一个节点

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

假设按照二进制堆的典型表示法，节点从 1 开始编号。选择任何有效的节点号并以二进制表示。忽略第一个（最重要的）1 位。其余位定义从根到该节点的路径；零表示左，一表示右。

例如，要到达节点 11 (=1011b)，从根开始，然后向左 (0)、向右 (1)、向右 (1)。

该算法可用于插入查找新节点的放置位置（按照节点 node_count+1 的路径），并在删除中查找倒数第二个节点（按照节点 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的代码

请注意，insert 中的遍历代码与上述算法略有不同，但仍然正确。

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）移动到被删除节点所占据的位置。两者都只能通过调整与其他节点的链接来工作，不涉及实际的数据移动。这些功能应该不难实现，上面提到的链接包括我的实现。

于 2016-12-27T01:53:44.210 回答
4

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

为此，您必须了解二进制遍历。我们所做的是。假设我们的堆大小为 6。我们将取数字 + 1，并将其转换为位。7的二进制表示是“111”。现在，请记住始终省略第一位。所以，现在我们只剩下“11”了。从左到右阅读。该位为“1”，因此，转到根节点的右子节点。那么左边的字符串是“1”，第一位是“1”。由于您只剩下 1 位，因此这一位会告诉您在哪里插入新节点。因为它是“1”，所以新节点必须是当前节点的右子节点。因此，该过程的原始工作是将堆的大小转换为位。省略第一位。根据最左边的位，如果是'1'则转到当前节点的右孩子，如果是'则转到当前节点的左孩子

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

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

我在这里发布源代码时遇到了麻烦，但是您可以参考我的博客获取源代码。在代码中，也有堆排序。这很简单。我们只是不断删除根节点。请参阅我的博客以获取数字说明。但我想这个解释可以。

希望我的回答对你有所帮助。如果有，请告诉我...！☺

于 2015-02-08T17:40:51.587 回答
2

对于那些说这是无用的练习的人来说，有几个（当然很少见）使用基于指针的解决方案更好的用例。如果堆的最大大小未知，则数组实现将需要在数组填满时停止并复制到新存储中。在具有固定响应时间约束和/或存在空闲内存但没有足够大的连续块的系统（例如嵌入式）中，这可能是不可接受的。指针树允许您以固定大小的小块增量分配，因此它不存在这些问题。

要回答 OP 的问题，不需要父指针和/或详细的跟踪来确定在哪里插入下一个节点或找到当前的最后一个节点。您只需要堆大小的二进制表示中的位来确定要遵循的左右子指针。

编辑刚刚看到Vamsi Sangam@对这个算法的解释。尽管如此，这里有一个代码演示：

#include <stdio.h>
#include <stdlib.h>

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

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

于 2016-12-27T05:33:38.927 回答
1

二叉堆是遵循堆属性的完全二叉树。就这样。可以使用数组存储它的事实既好又方便。但可以肯定的是，您可以使用链接结构来实现它。这是一个有趣的运动！因此，它最适合作为练习或更高级的数据结构（例如可融合、可寻址的优先级队列），因为它比数组版本涉及更多。例如，考虑 siftup/siftdown 程序，以及您需要正确进行的所有边缘切割/缝纫。无论如何，这不是太难，再一次，很好玩！

于 2014-04-03T11:05:11.970 回答
0

有许多评论指出，通过严格的定义，可以将二叉堆实现为一棵树，但仍将其称为二叉堆。

这就是问题所在——没有理由这样做，因为使用数组在各个方面都更好。

如果您进行搜索以尝试查找有关如何使用指针处理堆的信息，您将找不到任何信息——没有人会打扰，因为没有理由以这种方式实现二进制堆。

如果您在树上进行搜索，您会发现很多有用的材料。这就是我最初回答的重点。没有什么可以阻止人们这样做，但从来没有理由这样做。

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

当您需要内容取消引用它们时，制作这些指针的数组并在此数组中使用它们，就像您使用基于标准数组的堆一样。这将比任何其他实现系统的方式更好。

我想不出使用指针来实现堆的其他理由。

原答案：

如果你用指针实现它，那么它就是一棵树。堆之所以是堆，是因为您可以将子节点的位置计算为数组中的位置（2 * 节点索引 +1 和 2 * 节点索引 + 2）。

所以不，你不能用指针来实现它，如果你这样做了，你已经实现了一个树。

如果你搜索你会找到你的答案，实现树是有据可查的。

于 2013-11-01T03:50:09.443 回答
-2

我在互联网上搜索过（包括 SO），但找不到答案。

有趣，因为我在谷歌搜索后就找到了关于 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()不应该太难，当然你必须确保这些功能不会产生leftmostNode, rightmostNode, 或lastNode指向错误的地方。

TL;DR只需使用该死的数组。

于 2014-01-21T13:10:24.007 回答