I have implemented a Heap-Based Priority Queue in Java but my challenge now is implementing an efficient Iterator that has a definite (increasing or decreasing) order of traversal. Is there any algorithm that does this at constant auxiliary space and time complexity of O(n)? The O(nlogn) is quite trivial. Also, there is absolutely no subtlety in O(n) space algorithm. Please help if you can.
2
-
2O(n log n) is the best you can do with constant space. The lower bound on the number of comparisons for a comparison sort is Ω(n log n). The number of comparisons needed to heapify an array is O(n). So heapify is essentially doing one O(n) pass out of the log(n) passes needed to fully sort the array. Hence, if you can iterate the elements in the heap in sorted order in less than O(nlog(n) - n) time, then you've invented a new type of sorting algorithm that's faster than the theoretically best possible sorting algorithm.user3386109– user33861092022-04-14 06:17:33 +00:00Commented Apr 14, 2022 at 6:17
-
You can do it in constant space easily enough, if you're allowed to destroy the heap while you iterate.rici– rici2022-04-14 15:12:31 +00:00Commented Apr 14, 2022 at 15:12
Add a comment
|
1 Answer
No, there is no algorithm that iterates a heap in order with a time complexity of O(n).
An optimal comparison based sorting algorithm has a worst case time complexity of O(nlogn). If you could iterate a heap (which is comparison based) in ascending order with a time complexity of O(n), you'd have a comparison based sorting algorithm with a time complexity of O(n), which is not possible.
