Re: Optimizing basic operations
- Posted by DerekParnell (admin) Aug 05, 2013
- 5585 views
gimlet said...
Basically you are doing too much work. The only requirements we really need are:
1. That we know the minimum record for the top 100, the others do not concern us.
2. A data structure which will efficiently provide us with that (eg: a heap). See Wikipedia 'Heap (data structure)' only reverse the conditon so that root is the minimum and items are greater than or equal to their parent node.
This is a good solution as it uses constant space and an (optimal) single read of the data.
Yep, that's pretty much exactly what I suggested too. Only instead of a min-heap structure I just used a sorted sequence with a binary search for insertions - which would be much fast than a heap structure.
