问实现不使用数组的堆
EN

Stack Overflow用户

提问于 2014-06-24 09:14:08

回答 1查看 238关注 0票数 0

我正在为谷歌开发者的面试做准备，我被困在了一个关于堆的问题上。我需要将堆实现为动态二叉树(而不是数组)，其中每个节点都有一个指向父节点和两个子节点的指针，并且有一个指向根节点的全局指针。这本书问：“为什么这还不够？”

如何将标准树实现扩展到支持堆操作add()和deleteMin()？如何在这种数据结构中实现这些操作？

发布于 2014-06-29 09:21:28

你能保持节点总数的大小吗？如果是这样的话，那么很容易知道应该在哪里添加新元素，因为这几乎是一个完整的树。

关于deleteMin，我认为它不太有效，因为不能像数组(N/2)那样直接访问所有叶子。你应该走遍所有的路，直到你得到叶子，然后比较它们，很可能会花费O(n)。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/24382720

复制

相似问题

问实现不使用数组的堆EN