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.
Advertisement
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.