max-sheaps可以在同一个树本身内具有任意分支因子。
例如[8,5,3,1]，产生的一些堆可能是
8 or 8 or 8
/|\ | |
5 1 3 5 5 and so on.....
(a) / \ |
3 1 3
(b) |
1
(c)
为了我的目的，我认为树（a）与下面的树（d）和（e）相同
8 8
/|\ /|\ and so on.....
3 5 1 1 5 3
(d) (e)
编辑：
（1）我尝试过一种算法来生成所有可能的树，然后根据max-heap属性进行过滤。但显然这是指数级的，因此即使是一个包含10个以上元素的列表，在Python中也需要一段时间。
（2）我想构造那样只遵守max-heap属性而不是过滤的树，但是我不能用它来形成递归子问题。
这个比非限制树生成器简单得多。
有趣的是，对于k元素，有正确的(k-1)!可能的一般堆。 （如果我们生成堆的森林，就会有k!可能的森林，这相当于生成一个以新节点为根的单个堆。）
关键的见解是heap属性保证任何子树的最大元素是该子树的根（因此最大的元素是树的根）。由于我们不关心子节点的顺序，我们可以同意在每个节点按降序放置子节点，这将保证子树中的第二大元素将完全是该子树根的最左边的子节点。
因此，我们可以按顺序放置元素，迭代所有可能的展示位置。在我们将最大元素作为树的根之后，每个后续元素依次可以成为任何先前放置元素的最后一个（或唯一）子元素。 （所有先前放置的子项都比新元素大，因此将它放在第一个位置会保持规范的子顺序。当然，由于所有先前放置的元素都较大，因此新元素可以是其中任何元素的子元素。）
通过该程序，在已放置i元素的步骤中，对于下一个元素，可能存在i可能的放置位置。因此公式(k-1)!。
实现上述内容非常简单，虽然它只是一个功能性解决方案：候选树在每一步都被修改。 （这意味着如果您打算对其进行修改或保留以供将来参考，则需要对已生成的树进行完整复制。）
# This differs from the tree object in the other answer because
# in this tree, the kids are modified and must therefore be lists
class tree(object):
def __init__(self, root, kids=()):
self.root = root
self.kids = list(kids)
def __str__(self):
if self.kids:
return "(%s %s)" % (self.root,
' '.join(str(kid) for kid in self.kids))
else:
return self.root
# The main function turns each label into a singleton (leaf) node, and
# then calls the helper function to recursively stitch them together into
# heaps
def allheaps(labels):
if labels:
yield from genheaps(list(map(tree, labels)), 1)
def genheaps(nodes, i):
if i == len(nodes): yield nodes[0]
else:
# For each possible position for node i:
# Place it, recurse the rest of the nodes, restore the parent.
for j in range(i):
nodes[j].kids.append(nodes[i])
yield from genheaps(nodes, i+1)
nodes[j].kids.pop()
这是从8,5,3,1构建的六个堆：
>>> print('\n'.join(map(str,allheaps("8531"))))
(8 5 3 1)
(8 (5 1) 3)
(8 5 (3 1))
(8 (5 3) 1)
(8 (5 3 1))
(8 (5 (3 1)))
或者，以图解方式（手工完成）
(8 5 3 1) (8 (5 1) 3) (8 5 (3 1)) (8 (5 3) 1) (8 (5 3 1)) (8 (5 (3 1)))
8 8 8 8 8 8
/ | \ / \ / \ / \ | |
5 3 1 5 3 5 3 5 1 5 5
| | | / \ |
1 1 3 3 1 3
|
1
堆的数量是非根节点数量的因子的事实表明堆和置换之间存在同构。事实上，在上图的帮助下可以看到。
我们可以通过对树的后序深度优先遍历来将堆转换为置换。后序遍历保证walk中的最后一个节点将是根。
换句话说，从以根标签结尾的排列到堆，我们初始化一个空堆栈并从左到右扫描排列。在首先通过从堆栈顶部弹出任何较小的元素来填充其子列表之后，我们将每个标签推送到堆栈上。如果置换以最大元素结束，则它将是扫描结束时堆栈中唯一的元素。 （如果我们允许任意排列，我们将得到n!堆森林而不是(n-1)!扎根堆。）
这表明我们可以通过使用任何方便的枚举排列方法和从排列构造堆来枚举堆：
from itertools import permutations
from functools import reduce
def putlabel(stk, label):
kids=[]
while stk and stk[-1].root < label: kids.append(stk.pop())
stk.append(tree(label, kids))
return stk
def permtoheap(root, perm):
'''Construct a heap with root 'root' using the non-root nodes from
a postorder walk. 'root' should be larger than max(perm); otherwise,
the result will not satisfy the heap property.
'''
return tree(root, reduce(putlabel, perm, []))
def allheaps2(labels):
if labels:
yield from (permtoheap(labels[0], p) for p in permutations(labels[1:]))