|
-
November 7th, 2005, 11:56 PM
#1
The Best Structure
Hi,
What is the Best Structure for this goal!
the Add function in O(n) and fetch-meddian in O(1)?
Thanks!
-
November 8th, 2005, 12:03 AM
#2
Re: The Best Structure
a min-max heap!
its add would take O(n) but for finding its Meddian you should pick the max and min number and divide them on 2 which would take in O(1)
//I'm not sure what is your meaning from fetch-median?
-
November 11th, 2005, 06:46 PM
#3
Re: The Best Structure
What is add function complexity? if it's one of adding of just one element, you can as well use simple sorted array, inserting new element by bubble sort and picking median as center element of that array. 
"Programs must be written for people to read, and only incidentally for machines to execute."
-
November 11th, 2005, 06:57 PM
#4
Re: The Best Structure
I read it the same way as Robotact. A sorted array seems like the easiest solution.
Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
Supports C++ and VB out of the box, but can be configured for other languages.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote
