1

What's the good algorithm to keep the numbers sorted while it continually adds new numbers? Any built-in library in Python for it?

My idea is self-balanced binary searching tree

Insert: O(log(n))
Get top k numbers: O(k) do in-order travel
Get all sorted numbers: O(n) do in-order travel

Binary Heap works too but slower

Insert: O(log(n))
Get top k numbers: O(k*log(n)) pop out k numbers
Get all numbers: O(n*log(n)) pop out all

Thank you!

Denly
  • 899
  • 1
  • 10
  • 21
  • Not diretly answering the question, but maybe helpful: https://pypi.org/project/sortedcontainers/0.8.5/ – Bernhard Aug 08 '18 at 05:04
  • You seem to already know the algorithm (data structure) to use, so the most useful answer you're likely to get for the first part of your question is "yeah, use that". Although the structures you mentioned have different use cases - a heap is only really good at popping the first element (but if that's what you want, then... yeah, use that). – Bernhard Barker Aug 08 '18 at 05:26
  • What real problem are you going to solve? – MBo Aug 08 '18 at 05:34
  • I want to get the top k elements that dynamically added. Ideally by python. It is for coding interview, so I want to use the best algorithm. @MBo – Denly Aug 08 '18 at 08:46
  • So you want to keep top k elements during instant adding and sometimes retrieve them? In this case heap (for k elements!) is the best choice. Note that question was different... – MBo Aug 08 '18 at 09:09

1 Answers1

1

I've looked at built-in ones and it seems that there is no solution there.

But the sortedmap module provides the requested functionality and is based on std::map (red-black tree).

Mikhail Krassavin
  • 147
  • 3
  • 12