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

Java 中的 MinHeap 和 MaxHeap 实现

发布于 2024-12-28 20:05:41 字数 130 浏览 1 评论 0原文

我想知道java是否有任何集合可以帮助我实现minheap和maxheap。我知道我可以使用 PriortyQueue 数据结构来实现 maxheap。我们可以对 minheap 使用同样的方法吗？如果是，如何？

谢谢，马南

原文

分享到QQ

分享到微博

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

发布评论

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

可遇━不可求 2025-01-04 20:05:41

我认为你把它搞反了：堆是实现优先级队列的一种方式。至于最小/最大部分，只需编写适当的Comparator类即可。

回复收藏 0 原文

绾颜 2025-01-04 20:05:41

你的抽象水平在这方面有点落后。

堆是一棵像树一样的数据结构（注意，它实际上不必有一棵树，而是一种将数据点与其“子节点”相关联的方法（更多信息请参见下文）），它在数据结构之间具有非常特定的关系节点及其子节点。

相比之下，优先级队列是一个更抽象的概念。它是一个队列（具有 FIFO 数据访问模型的类似列表的数据结构），但实际上并不是 FIFO，而是首先返回最高优先级的对象。

就像在堆中，有不同的方法来实现底层结构一样，在优先级队列中也可以做许多不同的事情。使用堆作为优先级队列的底层结构的好处是您不必做任何更多的工作。只需根据优先级堆放值，当有人请求值时返回头部。

主要区别在于，堆是由它的树状属性和堆约束定义的，而优先级队列仅由它与其他队列的交互方式定义。

// A note on creating heaps
// Given that A is an array of n values indexed from 1 to n
// We can model a tree like structure buy stating that for any
// value i in (1,n) it's children are 2 * i and 2 * i + 1
// So with an array you can easily model a heap in this manner

You have your levels of abstraction a bit backwards on this.

A heap is a tree like ( note, it doesn't actually have to have a tree, but rather a method of relating points of data to their "children" ( see below for more )) data-structure which has very specific relation between nodes and their children.

A priority queue, in contrast, is a more abstract idea. It is a queue ( list like data structure with a FIFO data access model ) but rather than being actually FIFO it rather returns the object of greatest priority first.

Just like how, in a heap, there are different ways of implementing the underlying structure, so too in a priority queue one could do many different things. The benefit to using a heap as the underlying structure of the priority queue is that you don't have to do any more work. Just heap the values based on their priority and when someone requests a value return the head.

The major difference is that the heap is defined by it's tree like property and the heap constraint where as a priority queue is only defined by how it interacts with others.

// A note on creating heaps
// Given that A is an array of n values indexed from 1 to n
// We can model a tree like structure buy stating that for any
// value i in (1,n) it's children are 2 * i and 2 * i + 1
// So with an array you can easily model a heap in this manner

回复收藏 0 原文

~没有更多了~