Binary Search Heap Construction

Let's talk about algorithms!

Moderator: Board moderators

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

Binary Search Heap Construction

Post by kaushik_acharya »

I tried the recursive solution but got stack overflow for last two test case( (where input size is around 50,000)
My method is as suggested here:
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);
        if (maxPriorityIndex < (endIndex-1))
		Node* rightSubtreeRoot = construct_treap_recursive(maxPriorityIndex+1,endIndex,str);
        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: ... nstruction
But i wanted to figure out how to do using the method i was trying.
My experience with Fraudster khari

Post Reply

Return to “Algorithms”