C / C++ / MFC

Is it possible that the operation Insert AND DeleteMinimum on some data structure be done in constant time.

15-Mar-06 5:58

First you need to define the bases: speed limit and fine. Take this as an example:

const int SpeedLimit = 100; // 100 Miles Per Hour is the speed limit
const int BaseFine   = 500; // You pay 500 dolars (wow =P) if you reach 100 MPH
const int Additional = 10;  // 10 dolars for each extra mile

Then lets say that someone was running at 110MPH. It would be

int ActualSpeed = 110;
Ticket = BaseFine + ( ActualSpeed - SpeedLimit ) * Additional;

But be aware that this is only true if ActualSpeed is grater or equal to SpeedLimit, if it's lower you will wind up getting negative results, meaning that the cop would have to give money to the driver :-> Poke tongue | ;-P

Hope it helps

regards

hint_54

JERKII.SHANG14-Mar-06 14:57

Re: Is it possible that the operation Insert AND DeleteMinimum on some data structure be done in constant time.

14-Mar-06 14:57

Is there exist a data structure or Algorithms which support operation such like Insert AND DeleteMinimum in constant time?

Welcome to my site:
http://www.cntomorrow.com:3310

JERKII.SHANG14-Mar-06 15:02

Re: Is it possible that the operation Insert AND DeleteMinimum on some data structure be done in constant time.

14-Mar-06 15:02

I have seen that almost data structure I known so far does DeleteMinimum in O(log N) in worse case. but no algorithms can do this in O(1).

Welcome to my site:
http://www.cntomorrow.com:3310

David Crow15-Mar-06 2:56

David Crow

15-Mar-06 2:56

If the data structure is sorted, then you could achieve O(N) for deletion.

"Let us be thankful for the fools. But for them the rest of us could not succeed." - Mark Twain

"There is no death, only a change of worlds." - Native American Proverb

Re: Is it possible that the operation Insert AND DeleteMinimum on some data structure be done in constant time.

Dan McCormick15-Mar-06 4:04

Dan McCormick

15-Mar-06 4:04

I think you will find that Insert in constant time and DeleteMinimum in constant time are mutually exclusive.

An unsorted linked list (or even a vector) will allow for Insert to occur in constant time (just add the new element to the end of the list), but DeleteMinimum would require a search to find the value and could not be done in constant time.

On the other hand a sorted linked list would let you perform DeleteMinimum in constant time (because you know the minimum value will always be the first [or last] element of the list). Insert into the sorted list, however, could not be done in constant time since you would have to determine where in the list to place a new entry.

So, you have a trade off. Do you want Insert to be efficient or DeleteMinimum to be efficient? You need to understand how an application will use data in order to choose the optimum data structure.

Regards,
Dan

Remember kids, we're trained professionals.
Don't try this at home!

Re: Is it possible that the operation Insert AND DeleteMinimum on some data structure be done in constant time.

JERKII.SHANG15-Mar-06 13:13

15-Mar-06 13:13

Thanks, Dan McCormick. Thank you very much! Smile | :)

Welcome to my site:
http://www.cntomorrow.com:3310

Enable an dit box

beardy janggut14-Mar-06 14:33

beardy janggut

14-Mar-06 14:33

How can we enable an edit box after a button is clicked??

By using fprintf function, how can we print the character backslash (/) and aphostrophy (') in a .txt file???

HelpMe, I like your help

Re: Enable an dit box

Nibu babu thomas14-Mar-06 16:54

Nibu babu thomas

14-Mar-06 16:54

beardy janggut wrote:
How can we enable an edit box after a button is clicked??

m_your_edit.EnableWindow(TRUE);

beardy janggut wrote:
By using fprintf function, how can we print the character backslash (/) and aphostrophy (') in a .txt file???

The one you are showing is forward slash. You can print it by including it in the string.

For backslash you have to give two of them together '\\'. This will print a backslash character.

' can be printed as usual.

Nibu thomas
Software Developer

Re: Enable an dit box

ThatsAlok14-Mar-06 18:01

ThatsAlok

14-Mar-06 18:01

beardy janggut wrote:
How can we enable an edit box after a button is clicked??

On handller of Button:-
GetDlgItem(ID_OF_BUTTON)->EnableWindow(TRUE);

Array size

hint_5414-Mar-06 14:11

14-Mar-06 14:11

Hi there..

Anybody knows a way (if it is even possible) to determine an array's size. Something like this:

int GetSize( int* pArray )
{
  // Should return the number of elements on the array
}

int main( void )
{
 int* pArray;

 pArray = new int[ 20 ]; // MARK

 printf( "%d\n", GetSize( pArray ) * sizeof( int ) ); // Should output the number of bytes allocated at MARK

 return 0;
}

regards [[]]

hint_54

Michael Dunn14-Mar-06 16:53

Michael Dunn

14-Mar-06 16:53

You can determine the number of elements in a staticly-allocated array:

#define countof(x) (sizeof(x)/sizeof((x)[0]))
int arr[10];
size_t cElements = countof(arr);  // cElements gets 10

You cannot do this in a function, however, it's just not possible in C. That's why a function always takes an array (or pointer) and a count of elements when it has to know the array's size.

--Mike--
Visual C++ MVP Cool | :cool:

LINKS~! Ericahist | NEW!! PimpFish | CP SearchBar v3.0 | C++ Forum FAQ

hint_5415-Mar-06 5:46

15-Mar-06 5:46

Michael Dunn wrote:
That's why a function always takes an array (or pointer) and a count of elements when it has to know the array's size.

Could be speed optimization Dead | X|

Too bad.. I'll just have to do that

regards

hint_54

Stephen Hewitt14-Mar-06 17:07

Stephen Hewitt

14-Mar-06 17:07

Once you pass the array to the function it decays to pointer and size information is lost. Why not use a std::vector instead?

Steve

ThatsAlok14-Mar-06 18:13

ThatsAlok

14-Mar-06 18:13

Stephen Hewitt wrote:
Why not use a std::vector instead?

std::vector is one of best solution for dynamic array i believe... But ones should know how to deal with raw one too.. then he can able to differntiate what is good and what is bad!

"Opinions are neither right nor wrong. I cannot change your opinion. I can, however, change what influences your opinion." - David Crow

cheers,
Alok Gupta
VC Forum Q&A :- I/ IV

JERKII.SHANG15-Mar-06 13:20

15-Mar-06 13:20

If your array was created in heap, just like your code above, then you can use the function _msize to determine the size (in bytes) of your array.

int GetSize( int* pArray ){<br />
   return _msize((void *) pArray / sizeof(int));<br />
}

but if your array was created in stack, _msize does work properly.

Regards.

Welcome to my site:
http://www.cntomorrow.com:3310

JERKII.SHANG15-Mar-06 13:28

15-Mar-06 13:28

the code should be:

int GetSize( int* pArray ){
   return _msize((void *) pArray) / sizeof(int);
}

Good luck.

Welcome to my site:
http://www.cntomorrow.com:3310

hint_5415-Mar-06 13:34