Finding an appropriate data structure

Question

I have N keys.

I need to find a data structure which i can do with the following operations :

1. building it in O(N)

2. finding min in O(1)

3. deleting the median in O(logn)

4. finding the n/2+7-th biggest number

I thought about using a minimum heap (building is O(n),minimum is O(1) - root).

however, I'm having hard time finding a way to do 3 and 4.

I think the median suppose to be on of the leaves, but that's as far as i reached.

None

You may be looking for a B-Tree ( en.wikipedia.org/wiki/B-tree ). – Gallon

@Joe: Building the B-Tree is not O(N). – Tog

Answer 1

A popular question asked in Data Structures 1 exams/hws/tutorials. I'll try to give you some hints, if they don't suffice, comment, and I'll give you more hints.

1. Remember that you don't have to use just one data structure, you can use several data structures.
2. Recall the definition of a median: n/2 of the numbers are larger, and n/2 of the numbers are smaller
3. What data structures do you know that are built in O(n), and complex operations on them are O(logn) or less? - Reread the tutorials slides on these data structures.
4. It might be easier for you to solve 1+3 seperately from 1+2, and then think about merging them.

Battement

regarding 3 - that's the thing.. I can't think of such data structure. Searcing in O(Logn) usually involve a tree, but trees i now about can be built in no less then O(nlogn). I can binary search in O(logn), but again, sorting is O(nlogn). Some more hints please – None

Notice that you don't need to search for any value, only a single value - the n/2'th element. – Battement

I'm linking to the Technion tutorial slides of Data Structures 1. This should give you another clue. webcourse.cs.technion.ac.il/234218/Winter2009-2010/en/… – Battement

Hey anna, I was just checking your technion stuff. I'm studying at the open university, and I have a pretty big exam in a couple days so I'm doing some older exams, for practice. I haven't found the solution yet, hope it will pop soon. Thanks for your help – None

Hi Anna, i went through that link, the text are in Hebrew i guess. If you have the english version, can you please share it ? Thanks. – Jiles

@Bragaadeesh, these are the slides we used for the tutorials in Data Structures 1, and they indeed are in Hebrew. They were originally written by the course staff, for the course (which is given in Hebrew...). You can try looking for data structures 1 tutorials from American/British top universities, they might have some relevant information. – Battement

For the sake of other students here, I'll just tell that using heaps is the answer. I'm sure you can go on from here by yourself. – Battement

Answer 2

When you say building in O(n), do you mean that addition has to be O(n), or that you have to build a collection of elements in O(n) such that addition has to be O(1)?

You could augment pretty much any data structure with an extra reference to retrieve the minimal element in constant time.

For #3, it sounds like you need to be able to find the median in O(lg n) and delete in O(1), or vice versa.

For #4, you didn't specify the time complexity.

To other posters - this is marked as homework. Please give hints rather than posting the answer.

Grisby

I need to build the entire collection in O(n). And yes , I do need to find and delete the median in O(logn), but besides order statistic tree (which require nlogn for building) I can't think of other solutions. Help ? – None

Answer 3

Simple sorted Array would solve the problem for #2 #3 and #4. But the construction of it would take O(nn). However, there are no restrictions put on space complexity. I am thinking hard to use Hashing concept during the construction of the data structure which would bring down the order to O(n).

Hope this helps. Will get back if I find a better solution

Jiles