如何在haskell中并行排序未排序的二叉树叶子树？

可能重复：
Can I represent a Red-black tree as binary leaf tree?如何在haskell中并行排序未排序的二叉树叶子树？

下面仅仅是一个在只有叶项小二叶的树的例子，它们没有排序。如果不平坦化树，然后在再次构建排序树之前对其进行排序，是否可以并行排序（使用par和seq原语）。例如并行分类左右分支，然后对这两个分类进行最终排序。

 /\ 
    /\ 
    / \ 
    /\ /\ 
/\/\ 
    3 1 5 2

来源

2011-06-09 vis

您能否澄清一下：您是在尝试进行合并排序，还是更复杂？ – gatoatigrado 2011-06-09 02:27:36

是的，我想看看如何对这样的结构进行合并排序，然后我可以在之后添加任何并行性。类型def是：'data Tree = Leaf Int |节点（树）（树）' – vis 2011-06-09 02:33:24

Nom重新开放。这与该用户的其他问题不同，尽管存在一些重叠。 – sclv 2011-06-09 11:46:12

说“不平坦”是没有意义的，因为树必须被解构和重构反正：即使在您简单的例子，每一个节点必须改变，所以你不能从现有结构保存任何。阅读树，执行一个合适的排序算法（合并排序似乎是一个很好的选择，尤其是它适用于并行计算）并重构树。没有更好的办法。

来源

2011-06-09 06:44:14 Landei

谢谢。在我的情况下，我想要做的是并行排序左分支和右分支，然后在两个结果之间进行合并。所以合并排序确实是最好的。对于一棵更大的树，我可以在树中进一步下去，并行排列几个子树。但然后我仍然需要做一些事情：sortList（subTreeToList（subTree）） – vis 2011-06-09 11:19:10

如何在haskell中并行排序未排序的二叉树叶子树？

回答

相关问题