CLRS中给出的Build-Heap算法
BUILD-MAX-HEAP(A)
1 heap-size[A] ← length[A]
2 for i ← ⌊length[A]/2⌋ downto 1
3 do MAX-HEAPIFY(A, i)
它只产生几种可能情况中的一种。是否有其他算法会产生与上述算法不同的情况。 对于输入数组 A={4,1,3,2,16,9,10,14,8,7} Build-Heap 产生满足堆属性的 A={16,14,10,8,7,9,3,2,4,1}。 可能这是从数组构建堆的最有效算法,但数组的其他几种排列也具有堆属性。 当我生成数组的所有排列并对堆属性执行测试时。我得到了具有堆属性的数组的 3360 个排列。
Count1 16 9 14 4 8 10 3 2 1 7
Count2 16 9 14 4 8 10 3 1 2 7
Count3 16 9 14 4 8 10 2 1 3 7
Count4 16 9 14 4 8 10 2 3 1 7
Count5 16 9 14 4 8 10 7 2 1 3
Count6 16 9 14 4 8 10 7 2 3 1
Count7 16 9 14 4 8 10 7 1 3 2
Count8 16 9 14 4 8 10 7 1 2 3
Count9 16 9 14 4 8 10 7 3 1 2
Count10 16 9 14 4 8 10 7 3 2 1
...........................................................
Count3358 16 8 14 7 4 9 10 2 1 3
Count3359 16 8 14 7 4 9 10 3 2 1
Count3360 16 8 14 7 4 9 10 3 1 2
那么是否有不同的构建堆算法会给出与上述算法不同的输出或给出 3360 种可能结果中的一些?
一旦我们使用构建堆得到一个满足堆属性的数组。我们如何使用这个数组生成最大数量的其他案例。我们可以交换堆的叶节点来生成一些案例。有没有其他方法可以在不检查堆属性测试的所有排列的情况下获得更多可能的情况?
给定数组中值的范围并且所有值都是不同的。我们能说出满足堆属性的可能情况的总数吗?
最佳答案
任何堆构建算法都会对插入项的顺序敏感。如果您以不同的顺序提供相同的元素,即使是 Build-Heap 算法也会生成不同的堆。
请记住,在构建堆时,部分构建的部分必须在每次插入后保持堆属性。因此,这将限制可以由任何特定算法生成的不同排列。
关于algorithm - 在数组上构建堆算法。无需暴力破解即可生成结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13214013/