1

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得到一个满足heap属性的数组。我们如何使用这个数组生成最大数量的其他case。我们可以交换堆的叶子节点来生成一些case。有没有在不检查堆属性测试的所有排列的情况下获得更多可能情况的其他方法？

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

4

2 回答 2

0

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

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

于 2012-11-04T03:46:39.337 回答
0

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

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

于 2012-11-17T05:24:15.627 回答