Timeline for Most efficient known priority queue for inserts
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2020 at 10:30 | history | edited | CommunityBot | Commonmark migration | |
| Jul 27, 2012 at 17:31 | comment | added | edA-qa mort-ora-y | That makes sense. I should have though about the sorting limit more, since I've actually implemented the vEB tree (well,a trie, or radix, which appears to be similar in nature and have the same complexity). | |
| Jul 27, 2012 at 14:09 | comment | added | Juho | @edA-qamort-ora-y That's not a problem since there are such algorithms. The crucial fact (that really should be emphasized here I think) is that the priority-queue here is for exactly integers in a specific range. Likewise consider perhaps a more familiar case of sorting with a vEB-tree. With integers in the range $0$ to $M-1$ one can easily sort in $O(n \log \log M)$ time. | |
| Jul 27, 2012 at 12:49 | comment | added | edA-qa mort-ora-y | This would imply a sorting algorithm better than $O(n log n)$ since you you could simply insert all items, find-min and delete n times, giving you $O(n log log n)$ time. | |
| Jul 27, 2012 at 10:50 | history | edited | Juho | CC BY-SA 3.0 | fixed logs |
| Jul 20, 2012 at 7:02 | comment | added | A T | I'm sure we can do better. Revisit this question soon and you'll see some answers showing more efficient priority-queues :) | |
| Jul 19, 2012 at 19:57 | comment | added | Juho | Why can't we do better? As I understand it, the question is specifically asking for an optimal data structure, or perhaps optimal tradeoffs if you will. | |
| Jul 19, 2012 at 15:49 | history | answered | A T | CC BY-SA 3.0 |