当前位置：文江博客话题详情

堆排序获取父级

发布于 2024-12-12 14:11:38 字数 372 浏览 4 评论 0原文

要获取堆排序数组中节点的父节点，计算公式为 (index - 1) / 2。

但是，假设每个节点在数组中占用 4 个空格。要访问记录/节点，我必须访问该记录的四个记录的第一个位置。下面是一个示例：

如果父级从位置 4 开始，则左子级从位置 12 开始，右子级从位置 16 开始。获取左子级的方程式为 2*position + 4获得右子节点的方程为2*position + 8。

获得父级的方程式是什么？我需要一个方程来获取左子节点或右子节点的父节点，与 index-1/2 的方式相同。这可能吗？如果我需要两个单独的方程，那是行不通的，因为我真的不知道记录是左孩子还是右孩子。

谢谢你，

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一梦浮鱼 2024-12-19 14:11:39

查看以下 C# 最小堆。

    public int GetParent(int i, out int index)
    {
        double element = i;
        index = (int)Math.Floor((element - 1)  / 2);

        if(index < 0)
        {
            return 0;
        }

        return _collection[index];
    }

这适用于常规堆实现。

您可以在此处查看 MinHeap 实现的其余部分。

通常，堆结构由数组支持，有趣的是，堆希望从数组开始1 使计算父母和孩子变得容易。

如果您想修改子级、父级，正如您在问题中提到的那样，您应该考虑将 4 个节点包装在一个节点中，但保持堆的工作方式不变

Look at the following C# Min heap.

    public int GetParent(int i, out int index)
    {
        double element = i;
        index = (int)Math.Floor((element - 1)  / 2);

        if(index < 0)
        {
            return 0;
        }

        return _collection[index];
    }

This works for regular heap impl.

you can see the rest of the MinHeap implementation here.

Usually, heap structure is backed with an array and interestingly, heap wants to start from Array1 to make calculating parent and childs easy.

if you want to modify the child, parent as you mentioned in your problem, you should consider wrapping your 4 nodes in a node but keep how heap works the way it is

回复收藏 0 原文