合并具有线性复杂性的堆数组
如何将两个堆数组合并成一个平衡的堆数组，同时保持线性复杂度？我读过的很多关于堆合并的材料都需要O(nlogn)。
共有2个答案
我们有两个大小为N的堆。每个堆都可以表示为一个数组。参见父级和子级之间的关系。所以我们有两个堆排序的数组。我们需要通过将一个数组的所有元素添加到另一个数组的末尾来将这两个数组连接成一个数组。
所以现在我们有一个大小为2N的数组，但它不是堆排序的。要使数组堆排序，需要线性比较数，因此需要线性时间。（参见自下而上的堆构造-以O（n）构建堆的顺序）
有一种O（n）time算法（有时称为“heapify”），在给定n个总值的情况下，根据这些值创建最大堆。前面的答案描述了算法并解释了它的运行时间。您可以使用此算法合并两个最大堆，方法是创建一个新数组，存储这些最大堆中的所有值，并应用heapify算法从这些值中构造一个新堆。
但是，如果您知道您将经常合并堆，那么有比二进制堆更好的数据结构。例如，二项式堆、配对堆和倾斜堆都支持 O（log n） 时间内的合并。
希望这有帮助！
-
下面是数组上HEAPSORT的伪代码 很明显，BUILD-MAX-HEAP的复杂度为O（n），MAX-HEAPIFY的复杂度为O（h），其中h是具有最大logn值的堆的高度。 我不完全理解的是为什么HeapSort有nlogn的复杂性。我知道我们有n次迭代，每次迭代都有一个MAX-HEAPIFY。但是他MAX-HEAPIFY调用在每次迭代中都得到一个大小递减的HEAP。那么为什么每次迭代都有O（l
-
在研究合并k个排序的连续数组/向量的问题以及它在实现上与合并k个排序的链表有何不同时，我发现了两个相对简单的用于合并k个连续数组的朴素解决方案和一个基于成对合并的很好的优化方法，该方法模拟了mergeSort（）的工作原理。我实现的两个朴素解决方案似乎具有相同的复杂性，但在我进行的一个大型随机测试中，似乎一个比另一个效率更低。 我天真的合并方法如下所示。我们创建一个输出向量 我的第二个天真解决方案
-
我一直在使用java（jdk 6 hot spot JVM）进行垃圾收集。我希望社区能帮助我解决一些问题。 我的理解是： 1） 堆被分为 a）年轻一代-Eden和幸存者：新的对象和阵列被创建到年轻一代。次要的垃圾回收机制将在年轻一代中运行。对象，仍然活着，将从伊甸园空间移动到幸存者空间。 b）老一代/终身一代：主要收集将仍然活着的对象从年轻一代转移到老一代。 2）非堆分为 我想知道的是：
-
我主要是想理解在堆中插入一个新元素的大O和Omega背后的原因。我知道我可以在网上找到答案，但我真的喜欢有一个彻底的理解，而不是仅仅在网上找到答案，只是一味地记忆。 例如，如果我们有以下堆（以数组格式表示） 如果我们决定插入一个新元素“4”，那么我们的数组现在将如下所示 它将被放置在索引9中，由于这是第0个基于索引的数组，它的父数组将是索引4，也就是元素5。在这种情况下，我们不需要做任何事情，因为
-
找到给定n个数字集的中位数的一种方法是将它们分布在2堆中。1是一个包含较低n/2（ceil（n/2））数字的max-heap和一个包含其余数字的min-heap。如果以这种方式保持，中位数是第一堆的最大值（如果n是偶数，则第二堆的最小值）。这是我的c代码： 我们知道堆化操作具有线性复杂性。这是否意味着如果我们像上面的代码一样将数字一个接一个地插入两个堆中，我们就会找到线性时间的中位数？