如何在堆（几乎完整的树）树的最后一层找到最后（最右边）的节点？

Question

我试图在堆的最后一层找到最右边的节点（树表示 以便删除 min/max 堆中的特定元素。

几乎所有网上的人都写过用位于最低级别的堆中最右边的节点替换要删除的节点 - 我完全理解但是我怎么能找到最后一个节点？

根据我的解决方案：我有一个解决方案是在存储节点地址的同时使用级别顺序遍历（广度优先搜索）遍历该树（堆结构） - 一旦队列中只剩下一个没有子节点的元素，我将使用它进行替换。此示例中最右边的节点是 33:

是否还有其他 method/link 我可以使用，因为使用队列似乎很长？

Answer 1

让我们看一个完整的二叉树，忽略节点存储的值，但对节点进行编号as if they were stored in an array，从根部的1开始编号：如果我们从根节点遍历到任何目标节点（除了根节点本身），左边缘（红色）0，右边缘（蓝色）1，我们看到一个模式：

Path     Edges   Target (binary)
─────    ──────  ───────────────
1 → 2    0       1 0
1 → 3    1       1 1
1 → 4    0 0     1 0 0
1 → 5    0 1     1 0 1
1 → 6    1 0     1 1 0
1 → 7    1 1     1 1 1
1 → 8    0 0 0   1 0 0 0
1 → 9    0 0 1   1 0 0 1
1 → 10   0 1 0   1 0 1 0
1 → 11   0 1 1   1 0 1 1
1 → 12   1 0 0   1 1 0 0
1 → 13   1 0 1   1 1 0 1
1 → 14   1 1 0   1 1 1 0
1 → 15   1 1 1   1 1 1 1

从根到所需节点的路径与该节点数的二进制表示相同（根为1），忽略最高位二进制位！

所以，在一棵完整的树中，要到达第K个节点，根为1，首先求小于K的2的最大幂，然后根据下面的二进制数字，按降序排列，0 表示左边，1 表示右边。

假设我们的节点结构类似于

typedef  struct node  node;
struct node {
    struct node  *left;
    struct node  *right;
    /* plus node data fields */
};

然后找到第i个节点，i = 1为root，可以实现为

node *ith_node(node *root, const size_t i)
{
    size_t  b = i; 

    /* Sanity check: If no tree, always return NULL. */
    if (!root || i < 1)
        return NULL;

    /* If i is 1, we return the root. */
    if (i == 1)
        return root;

    /* Set b to the value of the most significant binary digit
       set in b. This is a known trick. */
    while (b & (b - 1))
        b &= b - 1;        

    /* We ignore that highest binary digit. */
    b >>= 1;

    /* Walk down the tree as directed by b. */
    while (b) {
        if (i & b) {
            if (root->right)
                root = root->right;
            else
                return NULL; /* Not a complete tree, or outside the tree. */
        } else {
            if (root->left)
                root = root->left;
            else
                return NULL; /* Not a complete tree, or outside the tree. */
        }

        /* Next step. */
        b >>= 1;
    }

    /* This is where we arrived at. */
    return root;
}

在实践中，如果你有一个包含 N 个节点的完整二叉树，ith_node(root, N) 将 return 指向最终节点的指针。

如果你想要路径，最低有效位是从根开始的第一个边缘，你可以使用例如

/* (*path) will contain the path to ith node, root being i=1,
   and the return value is the number of steps needed.
   Returns -1 if an error occurs. */
int  path_to_ith(const size_t i, size_t *path)
{
    size_t  b = i;
    size_t  p = 0;
    int     n = 0;

    if (i < 1)
        return -1; /* Invalid i! */

    /* Set b to the value of the most significant binary digit set. */
    while (b & (b - 1))
        b &= b - 1;        

    /* Ignore most significant digit. */
    b >>= 1;

    /* Reverse the rest of the bits in b, into p. */
    while (b) {
        p = (p << 1) + (b & 1);
        b >>= 1;
        n++;
    }

    /* Store path. */
    if (path)
        *path = p;

    /* Return the number of edges (bits) in path. */
    return n;
}

请注意，上面的函数基于完整的树：即，除了最后一层之外的所有层都被填充，最后一层的所有最左边的节点都被填充。也就是说，如果使用上图中所示编号的节点 N 被填充，则节点 1 到 N-1 也必须被填充。

以上示例中的逻辑有效。但是，由于示例代码是在没有经过适当审查的情况下一次性编写的，因此其中可能存在错误。因此，如果您对示例代码有任何问题，或者确实在这个答案的任何地方有任何问题，请在评论中告诉我，以便我可以根据需要进行检查和修复。

请注意，二叉堆通常使用数组表示。

（为了使用正确的数组索引，我们在这里切换到 zero-based 索引；即从这一点开始，根位于索引 0。）

节点没有指针。为了支持删除，我们通常将索引存储到节点所在的堆数组中，否则节点只有数据。（如果您需要更改键值，或删除除根之外的条目，您通常会添加一个指定当前堆数组索引的数据字段。不过，它确实有点慢，所以通常不需要。我会省略它为简单起见。）

typedef  double  heap_key;

typedef struct {
    /* Data only! */
} heap_data;

typedef struct {
    heap_key   key;
    heap_data *val;
} reference;

typedef struct {
    size_t     max;  /* Current max heap size, nodes */
    size_t     len;  /* Number of nodes in this heap */
    reference *ref;  /* Array of references to nodes */
} heap;
#define  HEAP_INIT { 0, 0, NULL }

static inline void heap_init(heap *h)
{
    if (h) {
        h->max = 0;
        h->len = 0;
        h->ref = NULL;
    }
}

请注意 heap 中的引用数组是根据需要动态 allocated/reallocated 的，因此堆的大小没有固有限制（当然内存除外）。

HEAP_INIT 宏允许在声明时初始化堆。换句话说，heap h = HEAP_INIT; 等价于 heap h; heap_init(&h);.

向这样的堆中添加新元素非常简单：

static int heap_add(heap *h, heap_data *d, const heap_key k)
{
    size_t  i;

    if (!h)
        return -1; /* No heap specified. */

    /* Ensure there is room for at least one more entry. */
    if (h->len >= h->max) {
        size_t     max;
        reference *ref;

        /* Minimum size is 15 references; then double up
           to 1966080 entries; then set next multiple of
           1024*1024 + 1024*1024-2. */
        if (h->len < 15)
            max = 15;
        else
        if (h->len < 1966080)
            max = 2 * h->len;
        else
            max = (h->len | 1048575) + 1048574;

        ref = realloc(h->ref, max * sizeof h->ref[0]);
        if (!ref)
            return -2; /* Out of memory; cannot add more. */

        h->max = max; 
        h->ref = ref;
    }

    i = h->len++;
    h->ref[i].key = key;
    h->ref[i].val = data;

    /* Omitted:  Percolate 'i' towards root,
                 keeping the heap order property for keys. */

    /* if (!i) "i is root";
       For all other cases, the parent is at index ((i-1)/2), and
       if (i&1) "i is a left child, sibling is (i+1)";
       else     "i is a right child, sibling is (i-1)";
    */

    return 0;
}

在堆数组中，如果有 n 个节点，则索引 i 处的节点（索引为 0 的根节点）有

Parent 在索引 (i - 1)/2 当且仅当 i > 0
离开 child 在索引 2*i+1 当且仅当 2*i+1 < n
右 child 在索引 2*i+2 当且仅当 2*i+2 < n

级别 k 节点的索引是连续的，从 (1 << k) - 1 到 (2 << k) - 2，包含（当根具有索引 0 和级别 0 时）。

具有索引 i 的节点（具有索引 0 和级别 0 的根）处于级别 k，是 floor(log2(i+1)) 或通过例如以下函数获得：

static inline size_t  ith_level(size_t  i)
{
    size_t  n = 0;
    size_t  t = (i + 1) / 2;

    while (t) {
        t >>= 1;
        n++;
    }

    return n;
}

同样，上述示例中的逻辑有效。但是，由于示例代码是在没有经过适当审查的情况下一次性编写的，因此其中可能存在错误。因此，如果您对示例代码有任何问题，或者确实在这个答案的任何地方有任何问题，请在评论中告诉我，以便我可以根据需要进行检查和修复。

如何在堆（几乎完整的树）树的最后一层找到最后（最右边）的节点？

How can one find the last (right most) node on the last level of tree which is a heap (almost complete tree)?

c

heap

queue

data-structures