在array.Generate结果上构建堆算法，而无需暴力强制

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)

它只产生几种可能的cases.Are中的一种，而其他算法将产生与上述算法不同的情况。对于输入数组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得到一个满足堆property.How的数组，我们可以生成最大数量的其他情况吗?使用这个array.We可以交换堆的叶子节点来生成一些cases.Is，有没有其他方法可以获得更多可能的情况，而不需要检查堆属性测试的所有排列？

给定数组中的值范围，并且所有值都为distinct.Can，我们是否可以说明满足堆属性的可能情况的总数？

Answer 1

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

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

Answer 2

给定一个堆，生成至少一些允许的排列是相当容易的。

节点并不关心它的两个子节点的相对大小。因此，您可以交换任何节点的子节点，然后对两个节点中较小的一个进行向上筛选，以确保为该子树维护heap属性(即，如果它小于其一个子节点，则将其与该子节点交换，并沿着该路径继续执行相同的操作，直到它到达一个大于任何一个子节点的点，或者它移动到足够靠近数组末尾的位置，使其成为叶节点。