Follow

wanted: a data structure that holds a list of N objects and has the following properties

insert(X) - adds X to the list if there is room for it. If there is no room, it compares X to the maximum value currently in the list. If it is less, the maximum value is removed and X is put in its place.

get_list() - returns the list. the order of the elements does not matter

essentially, this data structure stores the smallest N values that were passed into insert(X)

now I've got some efficiency needs

insert(X) should take O(log N) time (or O(1) if amortized), and get_list shouldn't take longer than O(N^2) or something. basically insert(X) gets called a *lot* and get_list only gets called at the very end

also, the data structure shouldn't take more than O(N) space.

I'm thinking I can just use a max heap for this, but I was wondering if there were better options that aren't necessarily heap-based 🤔

@SuricrasiaOnline shouldn't a simple tuple (top,L) work?

insert(x) = compare top to x. If top < x, set x = top. Push x to L.

insert is O(1) and get_list is O(1)

@zardoz did you mean top = x?

@SuricrasiaOnline oh and you can even be sneaky and put x into top_index.

@SuricrasiaOnline ah. I misread your requirements.

I think a max-heap might be exactly what you need.

@SuricrasiaOnline i'd probably just use a max-heap for this tbh

i think this is basically just 'find the N largest elements in a list of arbitrary size', so you might want to look into online selection algorithms?

@SuricrasiaOnline This is pretty much what heaps are for - being a sorted set and handling chaotic inserts - but you could do it with a regular list, early-out by comparing against the last element in the list, then binary search to insert the new value and trim down to size, gives you O(log(n)) insert and o(n) memory footprint. Though that depends on you finding a list structure with o(1) inserts and indexes, and I don;t know that you're going to find one. Technically a list structure with o(log(n)) inserts would also work

But yeah anyway. I don't remember what heap performance characteristics actually are, but I do know they were good enough to nearly linearize my pathfinder that one time, so, seal of approval from me

vx. weird gay cat@BestGirlGrace@social.illegalpornography.com@SuricrasiaOnline Would a modified binary search tree do this? especially if you store a pointer to the largest element .