将不同的元素插入二叉堆

Question

可以将数字 1,2,3,4,5 插入二叉堆的方式的数量，这样得到的二叉堆就是最小堆？

答案 = 8

============================================= =============================

我的看法 - 因为它是一个最小堆，所以最小值将位于根。

这将是最小堆

                             o   -------> root will be chosen in 1 way
                            / \
                           o   o 
                          / \ 
                         o  o

-> 左子树将是 4C3*1*2 方式，因为根节点将获得最小值，左右子树可以获得任何值。

-> 最后是右子树 => 1C1 = 1

总共 - 1*4C3*1*2*1 = 8。这个方法正确吗？

Answer 1

是的，你的正确答案是8。让我们考虑所有的安排。

令 LST = left subtree 且 RST = right subtree

first -1 固定在根（因为 1 是最低元素）。

第一种方式：我们可以在 LST 中有 (2,3,4) 而在 RST 中只有 5：这里 (2,3,4) 可以通过在 LST 中将 4 作为根来安排成两种方式

第二种方式：(2,3,5) 在 LST，它本身可以通过 2 种方式完成，并在 RST 保持 4

第三种方式：(2,4,5) 在 LST 和 3 在 RST

第 4 种方式：(3,4,5) 在 LST 和 2 在 RST

总路数 = 2*2*2*2 = 8 路

将不同的元素插入二叉堆

Inserting Distinct elements into a Binary Heap

algorithm

heap

data-structures