構建堆算法（一個或多個）上的array.Generate成果無暴力破解

Question

在CLRS給出的內建堆算法

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} 構建堆產生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

任何堆構建算法都會對項目插入的順序敏感。即使構建堆算法會生成一個不同的堆，如果您給它相同的元素，但是以不同的順序。

請記住，當您構建堆時，部分構建的部分在每次插入後都必須保持堆屬性。所以這將限制任何特定算法可能產生的不同排列。

Answer 2

給定一個堆，生成至少一些允許的排列是相當容易的。

節點不關心其兩個子節點的相對大小。因此，您可以交換任何節點的子節點，然後在兩個較小的節點上進行篩選，以確保該子樹的堆屬性得到維護（即，如果它小於其子節點之一，則將其交換與該子節點相同，並繼續沿着該路徑進行同樣的操作，直到它到達一個大於任一子節點的位置，或者移動到陣列的末端足夠靠近它的葉節點。