well at first, due to the average complexity, I've tried to use hash table and skip list... that's didn't work... i still think it is possible, its just that i cant make the average function in O(1)

second opinion is that the insert and update complexity makes me think about going for either a tree or a list with binary search... but again, what with the average...

i think they want us to use heap/hash/skip list...