CODEWITHSUNDEEP
data-structuresheaptime-complexity
simon anedra
simon anedra

Reputation: 3

Writing a data structure with O(n) initialization and O(1) lookup

Given an array a1, a2, a3, ... , aN

I want to create a data structure that supports the following requirements:

I tried to build the data structures with 3 max heaps but I can't initialize the heaps in O(n).

How can I figure it out?

Upvotes: 0

Views: 80

Answers (1)

David K
David K

Reputation: 3132

The so-called "median of medians" algorithm can find the kth smallest element in an unordered set in O(n) time. You want to apply this for k = n/5 and k = 4n/5.

The result of the algorithm is a partially-ordered array where the desired kth element is in location k. After putting the n/5th element in its place I think it is possible to put the 4n/5th element in its place without having to re-do the entire algorithm, but in any case it is still O(n).

Assuming you have O(1) random-access lookup in the array then your O(1) lookup requirement will be satisfied.

Upvotes: 2

Related Questions