Google : 构建特殊堆

A rooted binary tree with keys in its nodes has the binary search tree
property (BST property) if, for every node, the keys in its left
subtree are smaller than its own key, and the keys in its right
subtree are larger than its own key. It has the heap property if, for
every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an
integer i and an integer j. No two i values are equal and no two j
values are equal. We must assemble the nodes into a single binary tree
where the i values obey the BST property and the j values obey the
heap property. If you pay attention only to the second key in each
node, the tree looks like a heap, and if you pay attention only to the
first key in each node, it looks like a binary search tree.Describe a
recursive algorithm for assembling such a tree

标准的treap
测试题： http://poj.org/problem?id=2201

标准的treap
测试题：
Narashy 发表于 2011-6-18 07:44

Are you ACMer??

和以前的一个根据中序和前续遍历构建二叉树的题目一样的解法：

struct TREE_NODE
{
        int nLVal;
        int nRVal;
        TREE_NODE* pLft;
        TREE_NODE* pRgt;
};

bool SortLftVal(const TREE_NODE& node1, const TREE_NODE& node2)
{
        return node1.nLVal < node2.nLVal;
}

//Already sorted by the first value
TREE_NODE* _inner_construct(TREE_NODE nodes[], int n)
{
        assert(nodes);

        if (0 == n) return NULL;

        //find the corresponding index of node with second value the biggest
        int nIndex = 0;
        for (int i = 0; i < n; i++)
        {
                if (nodes[i].nRVal > nodes[nIndex].nRVal)
                        nIndex = i;
        }

        nodes[nIndex].pLft = _inner_construct(nodes, nIndex);
        nodes[nIndex].pRgt = _inner_construct(nodes+nIndex+1, n-nIndex-1);

        return &nodes[nIndex];
}

TREE_NODE* ConstructBSTHeapTree(TREE_NODE nodes[], int n)
{
        assert(nodes && n>0);

        sort(nodes, nodes+n, SortLftVal);

        return _inner_construct(nodes, n);
}

回复 4# wwwyhx

这个做法最坏情况下是o(n^2)的，poj上那题很可能过不了吧

回复  wwwyhx

这个做法最坏情况下是o(n^2)的，poj上那题很可能过不了吧
Narashy 发表于 2011-6-23 02:32

    啊？？?????????????????????????????????

啊？？?????????????????????????????????
wwwyhx 发表于 2011-6-24 18:07

    你可以试着提交下看看啊，可能会得到 time limit exceeded 的结果

wwwyhx 发表于 2011-6-24 18:07
啊？？?????????????????????????????????

想到个O(nlogn)的解法，不过要排序两次，分别对两个关键字，描述起来比较复杂

实际上可以RMQ吧……对value排序，然后不停地RMQ得到根节点，最多查询N次……