java – 通过二叉树结构实现的二进制堆

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 通过二叉树结构实现的二进制堆，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1305字，纯文字阅读大概需要2分钟。

内容图文

对于赋值,我们被指示创建一个通过二进制堆实现的优先级队列,而不使用任何内置类,并且通过使用数组来存储排队对象,我已经成功完成了.但是,我有兴趣学习如何使用实际的树结构来实现另一个队列,但是这样做我遇到了一些问题.

如何跟踪我将执行插入和删除的节点？我尝试使用链接列表,它在插入每个节点时附加它们 – 从第一个列表节点开始添加新子节点,并从另一端删除.然而,当元素在树中重新排列时,这会分崩离析,因为孩子被添加到错误的位置.

编辑：也许我应该澄清 – 我不知道我怎么能找到最后被占用的和第一个未被占用的叶子.例如,我总是能够告诉最后插入的叶子,但是如果我要删除它,当下次删除项目时,我怎么知道要删除哪个叶子？插入相同 – 在当前叶子有两个孩子占了之后,我怎么知道哪个叶子跳到下一个？

解决方法:

二进制堆的树实现使用complete tree [或几乎完整的树：每个级别都已满,除了最深的一个].
你总是’知道’哪一个是最后一个被占用的叶子 – 你从[删除它]并在它改变后修改它是O(logn)所以它不是问题],你总是’知道’哪个是第一个非占用的叶子,在其中添加元素[并再次修改它也是更改后的O(logn)].

算法思路很简单：
insert：将元素插入第一个非占用的叶子,并使用heapify [sift up]将此元素放到堆中的正确位置.

delete_min：将第一个元素替换为最后一个被占用的叶子,并删除最后一个被占用的叶子.然后,堆积[筛选]堆.

编辑：请注意,delete()可以对任何元素进行,而不仅仅是head,但是 – 找到要用最后一个叶子替换的元素将是O(n),这将使这个op昂贵.因此,delete()方法[除了head]通常不是堆数据结构的一部分.

内容总结

以上是互联网集市为您收集整理的java – 通过二叉树结构实现的二进制堆全部内容，希望文章能够帮你解决java – 通过二叉树结构实现的二进制堆所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---