algorithm - 在数组上构建堆算法。无需暴力破解即可生成结果

Question

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 种可能结果中的一些？

一旦我们使用构建堆得到一个满足堆属性的数组。我们如何使用这个数组生成最大数量的其他案例。我们可以交换堆的叶节点来生成一些案例。有没有其他方法可以在不检查堆属性测试的所有排列的情况下获得更多可能的情况？

给定数组中值的范围并且所有值都是不同的。我们能说出满足堆属性的可能情况的总数吗？

Answer 1

任何堆构建算法都会对插入项的顺序敏感。如果您以不同的顺序提供相同的元素，即使是 Build-Heap 算法也会生成不同的堆。

请记住，在构建堆时，部分构建的部分必须在每次插入后保持堆属性。因此，这将限制可以由任何特定算法生成的不同排列。