k-smallest-datastructure

Year 3 - Advanced Algorithms

Problem definition: "A very large number of random numbers are added to a list. Design and implement an efficient data structure that will maintain a separate list of the k smallest numbers that are currently in the list. Space efficiency must be O(k + n). How would you handle deletions? Perform an amortised analysis of your data structure."