## Binary Search Heap Construction

Let's talk about algorithms!

Moderator: Board moderators

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

### Binary Search Heap Construction

http://poj.org/problem?id=1785

I tried the recursive solution but got stack overflow for last two test case(http://www.informatik.uni-ulm.de/acm/Locals/2004/) (where input size is around 50,000)
My method is as suggested here: http://www.stanford.edu/class/cs97si/assn3.html
i.e. Find the root, divide-and-conquer

Code: Select all

``````class Node
{
string label;
int priority;
Node* left;
Node* right;
}

class Treap
{
std::vector<Node*> vecNode_;
Node* root_;
}

Node* Treap::construct_treap_recursive(unsigned int beginIndex, unsigned int endIndex)
{
// create sub-tree of nodes [beginIndex,endIndex) //endIndex excluded
// root of the subtree is the node which has highest priority
if (endIndex - beginIndex == 1)
{
return vecNode_[beginIndex];
}

// get the max priority index in the range [beginIndex,endIndex)
Node* curRoot = vecNode_[maxPriorityIndex];

if (maxPriorityIndex > beginIndex)
{
Node* leftSubtreeRoot = construct_treap_recursive(beginIndex,maxPriorityIndex,str);
curRoot->setLeft(leftSubtreeRoot);
}

if (maxPriorityIndex < (endIndex-1))
{
Node* rightSubtreeRoot = construct_treap_recursive(maxPriorityIndex+1,endIndex,str);
curRoot->setRight(rightSubtreeRoot);
}

return curRoot;
}

//The call:
root_ = construct_treap_recursive(0,vecNode_.size());
``````
Though I haven't written here, but the output string also gets formed during the treap construction.

My question:
a) Recursion is bound to hit stack overflow given the size of data. Am i right?
b) I am not able to figure out how to change this to iterative one. Can anyone give me a hint.
c) Though the treap can be constructed using this: http://en.wikipedia.org/wiki/Cartesian_ ... nstruction
But i wanted to figure out how to do using the method i was trying.
My experience with Fraudster khari