c – 是否可以进行有效的基于指针的二进制堆实现？

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

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

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

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

>对于插入：如果最后一个节点是左子节点,请继续将新节点作为父节点的右子节点插入.否则……从最后一个节点开始.只要当前节点是正确的子节点,就向上移动.如果未到达根,则移动到右侧的兄弟节点(必然存在).然后(无论是否到达根),尽可能向下移动到左侧.继续插入新节点作为当前节点的左子节点.
>对于remove：如果最后一个节点是root,则继续删除root.否则……从最后一个节点开始.只要当前节点是左子节点,则移动到兄弟节点左侧节点(必然存在).然后(无论是否到达根),尽可能向下移动到右侧.我们到达倒数第二个节点.

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

>删除时,有两种特殊情况：当删除最后一个节点时(取消@L_489_35@节点并更改最后一个节点指针),以及何时删除倒数第二个节点(不是很特殊,但必须是在用最后一个节点替换已删除的节点时考虑.
>在堆中向上或向下移动节点时,如果移动影响最后一个节点,则必须更正最后一个节点指针.

很久以前我已经实现了这一点.如果它可以帮助某人,here is the code.在算法上它应该是正确的(也经过了验证的压力测试),但当然没有保证.

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

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

假设节点从1开始编号,根据二进制堆的典型符号.选择任何有效的节点号并以二进制表示.忽略第一个(最重要的)1位.其余位定义从根到该节点的路径;零表示左,一表示右.

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

可以在insert中使用此算法来查找新节点的放置位置(遵循节点node_count 1的路径),并在remove中找到倒数第二个节点(遵循节点node_count-1的路径).

这种方法在libuv中用于定时器管理;见their implementation of the binary heap.

基于指针的二进制堆的有用性

这里的许多答案甚至文献都说基于数组的二进制堆实现是非常优越的.但是我对此提出质疑,因为有些情况下不希望使用数组,通常是因为数组的大小不是预先知道的,并且数组的按需重新分配不被认为是可接受的,例如由于延迟或可能性分配失败.

libuv(一个广泛使用的事件循环库)使用带指针的二进制堆的事实进一步说明了这一点.

值得注意的是,Linux内核在少数情况下使用(基于指针的)红黑树作为优先级队列,例如CPU scheduling和timer management(与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具有high_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)移动到被删除节点所持有的位置.两者都只通过调整与其他节点之间的@L_489_35@来工作,没有涉及的实际数据移动.这些功能应该不难实现,并且所提到的@L_489_35@包括我的实现.