|
Hi Frnds,
I am trying to do the heap implementation.
I was following the algorithm explained in cormen....
#include "MyHeap.h"
void MyHeap::Build_Max_Heap(int * array, int length)
{
for (int i= (length/2); i>=0 ; i--)
{
Max_heapify(array, i, length);
}
}
void MyHeap::Max_heapify(int * array, int index, int length)
{
int left = ((2 * index) + 1);
int right = ((2 * index) + 2);
int largest;
if ((left <= length) && (array[left] > array[index]))
{
largest = left;
}
else
{
largest = index;
}
if ((right <= length) && (array[right] > array[largest]))
{
largest = right;
}
if (largest != index)
{
swap(array[largest], array[index]);
Max_heapify(array, largest, length);
}
}
void MyHeap::swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
void MyHeap::print(int * array, int length)
{
for (int i = 0; i< length; i++)
{
cout<<array[i]<<"\t";
}
}
int main()
{
int array[] = {14, 10, 1, 8, 7, 9, 3, 2, 4, 16};
MyHeap h;
h.print(array, 10);
h.Build_Max_Heap(array, 10);
h.print(array, 10);
int x;
cin>>x;
return(0);
}
For some input it is working.
For some it is not..
for the given input this is the output I am getting..
16 14 9 8 10 1 3 2 4 7
Thanks in advance...
|
|
|
|
|
pavarathyRock wrote: I was following the algorithm explained in cormen....
You forgot to explain what you're trying to do in the comments...
All we currently know is that you're failing, not what you need to do.
Iain.
I have now moved to Sweden for love (awwww).
If you're in Scandinavia and want an MVP on the payroll (or happy with a remote worker), or need cotract work done, give me a job! http://cv.imcsoft.co.uk/[ ^]
|
|
|
|
|
16 14 9 8 10 1 3 2 4 7 looks like a correct heap to me, now I may have made a mistake, but it looks like:
16
/ \
14 9
/ \ / \
8 10 1 3
/ \ /
2 4 7
Which is a correct heap, no?
|
|
|
|
|
But here
16
/ \
14 9
/ \ / \
8 10 1 3
/ \ /
2 4 7
10 is coming after 9 . As per heaps definition the root should contain largest element right..
|
|
|
|
|
No it doesn't, the layout got messed up here, but that 10 is below the 14 and the 1 and 3 are below the 9.
|
|
|
|
|
Thanks herald for the help.....
I think my implementation is correct.
I have tried to print the heap as follows.
int main()
{
int array[] = {14, 10, 1, 8, 7, 9, 3, 2, 4, 16};
MyHeap h;
h.print(array, 10);
h.Build_Max_Heap(array, 10);
cout<<"Initial Heap\n";
h.print(array, 10);
cout<<endl;
int maxSize = 10;
while (maxSize > 0)
{
cout<<array[0];
cout<<endl;
for (int d = 0;d < maxSize; d++)
{
array[d] = array[d + 1];
}
maxSize--;
h.Build_Max_Heap(array, maxSize);
}
int x;
cin<<x;
return(0);
}
It was giving the correct output.
The main cause for this doubt is that I AM A FOOOL. I blindly believed the output given in the book.
I didn't even try to print the output and check.......
Thanks frnd thank you very much.....
and thanks for all others for your help.
|
|
|
|
|
Lol you're welcome, but you didn't spell my name right 
|
|
|
|
|
pavarathyRock wrote: void MyHeap::Max_heapify(int * array, int index, int length)
{
int left = ((2 * index) + 1);
int right = ((2 * index) + 2);
...
The first time Max_heapify() is called, left equals 11 and right equals 12.
pavarathyRock wrote: if ((left <= length) && (array[left] > array[index]))
left is then used to access array, which is indexed 0-9.
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
Hello,
I am adding ints in the CListBox by converting them into a CString . Can I add ints directly so that i dont have to sort the ints in the listbox
?
Pritha
|
|
|
|
|
In my understanding we can add only string to the items. the reason is listbox is not supposed to work with int only. you can store additional information to an item by "SetItemData" but AddString must be called and the item should exist.
prithaa wrote: Can I add ints directly so that i dont have to sort the ints in the listbox
I'm not clear with this. can you explain?
-Sarath.
"Great hopes make everything great possible" - Benjamin Franklin
|
|
|
|
|
Thanks for your reply
Actually I want to add ints in the ascending order in the list box .
but now when i add ints in the form of CString to the list box the list box is sorted in the CString sorted order that is
1
10
11
12
2
21
22
23
so will I have to sort the ints myself and the list box must be created without LBS_SORT
Pritha
|
|
|
|
|
You just remove the LBS_SORT and format the int to string and add it. Formatting to a string is that costly?
-Sarath.
"Great hopes make everything great possible" - Benjamin Franklin
|
|
|
|
|
|
Hello,
I have a resource editor dialog box compiled with Visual Studio 2003. The width is about 1300 pixels. On screens wider than this it works fine. The entire dialog shows and I can resize the right edge to smaller and back to full size.
If the screen width is less than the dialog width then I have a problem. As i would expect, the right side of the dialog box is clipped at the screen boundary. I can resize it smaller and back to this clipped size.
I drag the dialog box to the left then try resizing it. I can only make it smaller and bring it back to the original clipped size, even though this is nowhere near the screen boundary.
How do I setup the dialog box so that it can be resized to include all of the right end of the box?
Tom
|
|
|
|
|
See WM_GETMINMAXINFO[^]
You may be right
I may be crazy
-- Billy Joel --
Within you lies the power for good - Use it!
|
|
|
|
|
Hi All,
I’m developing a function driver 64bit, on “Windows 64 bit Standard Edition”.
I encountered with two issues:
1.Failed to pass pointer buffer (more then 16 Mb size) from 64 / 32 bit application To the 64 bit Driver (probe & lock mechanize fails).
2.Failed to map in 64 bit Driver more then 1 Gb memory (using MmMapIoSpace api).
I will appreciate your assistance.
Thanks.
modified on Sunday, July 5, 2009 9:27 AM
|
|
|
|
|
Where to get source code of any example of race condition. I need to simulate it using some sample. I tried to google it but not succeed. If any body having any idea would be better.
SNI
|
|
|
|
|
<br />
CAR raceCar = new CAR();<br />
CAR raceCar2 = new CAR();<br />
<br />
raceCar.WaitForStartFlag();<br />
raceCar2.WaitForStartFlag();<br />
<br />
while(RACING)<br />
{<br />
raceCar.RACE_!!!_();<br />
raceCar2.RACE_!!!_();<br />
}<br />
<br />
this is my old race condition codez sample 
|
|
|
|
|
SNI wrote: I need to simulate it using some sample.
See here.
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
this is pretty easy .. create a console app with two threads. one of them prints out 10xA, the other one 10xB.
Don't try it, just do it! 
|
|
|
|
|
I need urgent help regarding this.can anyone please convert this algorithm into c++ program.Its very important for me..pleaseee 
Staff Removal Algorithm.
procedure
STAFFLINEREMOVAL(IMAGE,STAVES)
threshold = 2∗staffHeight;
tolerance = 1+ceil(staffHeight/3.0);
IMAGE REMOVE = copy(IMAGE);
for nvalid = 0 to STAVES size do
Point2D staff = validStaves[nvalid];
for i = 0 to staff size do
col =staff[i].x;
refRow =staff[i].y;
row = refRow;
pel = valuePixel(IMAGE,IMAGE REMOVE)
decrement/increase the reference row until one
pixel different from white pixel (dist1/dist2) is found;
if dist1 ≤ max(1,min(dist2,tolerance)) then
refRow− = dist1;
else
if dist2 ≤ max(1,min(dist1,tolerance))
then
refRow+ = dist2;
else
continue;
end if
end if
Count the number of decrements/increase on
the reference row until the black pixel changes to white
pixel (run);
if run ≥ threshold then
continue;
end if
remove the vertical black sequences on the IM-
AGE;
end for
end for
end procedure
|
|
|
|
|
That doesn't look too hard.
How far have you got doing it yourself? What are you having problems with?
Have you written any code to try to do it?
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
|
Actually i tried writing but im not so proficient in c++.But it is compulsory to write in c++ so im helpless.Please do the needful.I shall be very grateful 
|
|
|
|
|
Why not try, and see how you get on ? There are plenty of people on here who will help on specific problems, but they won't do your homework for you !! (You wouldn't learn anything that way, would you ?)
Doug
|
|
|
|
|
Why is it "compulsory" to use C++?
If it's for a college course, you should be learning what you need, not relying on others to do your homework.
If it's for your job, you should only be taking on work you're capable of doing, or explaining to your boss that you don't have the ability for certain tasks.
Whatever the reason, if you want someone to do work for you, then you're going to have to pay them for it. I don't work for free for my company, and I've no intention of doing it in my spare time.
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
