can anybody tell why this code is not giving correct output for finding
second smallest using tournament method?
my approach is same as @Don approach
On Wed, Sep 5, 2012 at 12:16 PM, shashi kant <shashiski...@gmail.com> wrote:
> Heap's good but the i think problem clearly mentions "Tournament sort"
> use this
> https://blogs.oracle.com/malkit/entry/finding_kth_minimum_partial_ordering
>
> although you can do a Inplace tournament sort ...swapping the
> corresponding elements
> level 1. adjacent pairs
> level 2: between pairs apart by 1 place n so on (2,4,8..)
> until there is only one element left in there without a pair.....this
> gives u least element
>
>
> Now instead of using a "Multimap" , use a simple array with size equal to
> original array and store the element that defeated each corresponding
> element.
>
> Get all those elements defeated by the least element ... that number
> should be of order O(n)
> get the second least element out of it in O(n) time.
>
>
>
> *Shashi Kant *
> *"Think positive and find fuel in failure"*
> http://thinkndoawesome.blogspot.com/
> *System/Software Engineer*
> *Hewlett-Packard India Software Operations.
> *
>
>
>
> On Wed, Sep 5, 2012 at 4:11 AM, Dave <dave_and_da...@juno.com> wrote:
>
>> @Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
>> http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
>> .
>>
>> Dave
>>
>> On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
>>
>>> Constructing a max-heap is O(n*log n)
>>>
>>> However, the problem asked for a solution using tournament method.
>>> If you ignore that requirement, an O(n) solution is trivial, and
>>> doesn't require the additional storage of a heap:
>>>
>>> int first = max(A[0], A[1]);
>>> int second = min(A[0], A[1]);
>>> for(i = 2; i < N; ++i)
>>> {
>>> if (A[i] >= first)
>>> {
>>> second = first;
>>> first = A[i];
>>> }
>>> else if (A[i] > second)
>>> second = A[i];
>>> }
>>>
>>> // First and second now contain 1st and 2nd largest values in A
>>>
>>> Don
>>>
>>> On Sep 3, 5:04 am, bharat b <bagana.bharatku...@gmail.com> wrote:
>>> > Construct a max-heap --> O(n)..
>>> > call delete() 2 times .. --> O(logn)..
>>> > ===> O(n) time..
>>> >
>>> >
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
//To implement tournament code...
#include<iostream.h>
#include<math.h>
#define size 10
class node
{
public:
char c;
int freq;
int beaten;
node *left,*right;
node *parent;
node(char c1=0,int freq1=0,node *l=0,node *r=0)
{
c=c1;
freq=freq1;
left=l;
right=r;
beaten=freq1;
}
};
class array
{
public:
node *root;
array()
{
root=0;
}
int size1;
int heapsize;
int length;
node *b[size];
node *a[size];
void insert();
void buildheap();
void minheapify(int i);
node* extractmin();
void heapinsert(node *p);
void tour();
void display();
void display1(node *);
void decrease(int i);
void traverse()
{
traverse(root);
}
void traverse(node*);
void minimum();
int left(i)
{
return 2*i;
}
int right(i)
{
return 2*i+1;
}
};
//Min heap
void array::buildheap()
{
heapsize=length;
for(int i=(floor(length/2));i>=1;i--)
{
minheapify(i);
}
}
void array::minheapify(int i)
{
int l,r,smallest;
node *temp;
l=left(i);
r=right(i);
if(l<=heapsize && a[l]->freq < a[i]->freq)
{
smallest=l;
}
else
{
smallest=i;
}
if(r<=heapsize && a[r]->freq < a[smallest]->freq)
{
smallest=r;
}
if(smallest!=i)
{
temp=a[i];
a[i]=a[smallest];
a[smallest]=temp;
minheapify(smallest);
}
}
void array::heapinsert(node* k)
{
heapsize=heapsize+1;
a[heapsize]=k;
decrease(heapsize);
}
void array::minimum()
{
cout<<a[1];
}
node* array::extractmin()
{
node* min;
if(heapsize<1)
return 0;
min=a[1];
a[1]=a[heapsize];
heapsize=heapsize-1;
minheapify(1);
return min;
}
void array::decrease(int i)
{
node* temp;
while(i>1 && a[i/2]->freq > a[i]->freq)
{
temp=a[i/2];
a[i/2]=a[i];
a[i]=temp;
i=i/2;
}
}
void array::insert()
{
char c1;
cout<<"Enter length"<<endl;
cin>>length;
for(int i=1;i<=length;i++)
{
a[i]=new node();
cout<<"Enter the character"<<endl;
cin>>c1;
a[i]->c =c1;
cout<<"Enter frequency of the character you entered"<<endl;
cin>> a[i]->freq;
a[i]->beaten=a[i]->freq;
b[i]=a[i];
}
buildheap();
heapsize=length;
}
void array::tour()
{ node *x,*y;
for(int i=1;i<=(length-1);i++)
{
node* z=new node();
x= extractmin();
y= extractmin();
x->parent =z;
y->parent =z;
z->left =x;
z->right =y;
if(x->freq<y->freq){
z->freq =x->freq;
if(x->beaten>y->freq) {
x->beaten=y->freq;
z->beaten=y->freq;}
}
else {
z->freq=y->freq;
if(y->beaten>x->freq) {
y->beaten=x->freq;
z->beaten=x->freq;}
}
heapinsert(z);
cout<<"\n";
cout<<z->beaten;
}
root =extractmin();
cout<<root->beaten;
cout<<root->freq;
}
void array::display()
{
for(int i=1;i<=length;i++)
{
cout<<"\nCode for\t"<<(b[i]->c)<<" ";
display1(b[i]);
}
}
void array:: display1(node* t)
{
if(t!=root){
if(t->parent->left==t)
{
display1(t->parent);
cout<<"0";
}
else
{
display1(t->parent);
cout<<"1";
}
}
}
void array::traverse(node* p)
{
if(p!=0)
{
traverse(p->left);
cout<<p->freq<<" ";
traverse(p->right);
}
}
void main()
{
array o1;
o1.insert();
o1.tour();
//cout<<"Displaying"<<endl;
//o1.display();
cout<<"\nTraversing"<<endl;
o1.traverse();
}
