最大堆之间并排序堆

我想知道，当我们可以排序与Collections.sort方法的堆栈所以为什么我们需要一个像最大堆一个新的数据结构？谢谢最大堆之间并排序堆

2010-06-13 user355002

我没有太多的意义来分类堆栈。你能举一个你为什么要这样做的例子吗？我还没有听说过“最大堆”数据结构，你可以添加一个链接到它的javadoc？ – 2010-06-13 08:17:34

我们有自己的两种堆数据结构（Min heap and max heap） – user355002 2010-06-13 08:27:59

@Peter heap =优先级队列，这是Collections中使用的名称。同意，“排序堆栈”是没有意义的。 – 2010-06-13 08:49:00

栈和堆具有完全的区别不同的性质和用途。

LIFO需要堆栈。排序它将花费O（N * logN），推/弹出O（1）。

堆需要用于例如优先级队列，得到了最小/最大元件将花费O（1），插入元件为O（log（N））

需要确定的使用模式和目标，然后决定你需要什么。

2010-06-13 08:46:25 Drakosha

Collections.sort需要O（n log n）。因此，尽管在每次操作之后通过调用Collections.sort来模拟堆列表是正确的，但它不必要的低效。堆允许您插入任何元素或检索O（log n）中的顶层元素。

Collections.sort罚款时，你必须排序一次。如果在修改集合时必须保持集合的排序顺序，则使用排序后的数据结构（例如堆或树）会更有效。

2010-06-13 11:08:22 meriton

这取决于您的要求。堆栈和堆中的访问模式完全不同。堆栈实现为简单列表，而堆实现为优先级队列。在堆栈中排序时间为O（nlog（n）），同时您可以在O（log（n））时间内提取最大优先级元素（最大值/最小值）。

所以你的问题在哪里使用MaxHeap，想想你需要从1000中找到第7大元素的场景。在堆栈中先排序然后从开始排序（降序排序）将是解决方案，但使用MaxHeap必须提取元素7次，第7次将是解决方案。所以这取决于你的情况，哪一个可以让你更好。

2010-06-13 18:12:50

回答