Question about task 15.19 - The view from the above

#1

Hello all!

I’m currently solving the task 15.19 and have a question:
why we use the BST for storing interval heights instead of Index Max-Heap?
I can assume that using max-heap will improve performance
as taking the max value will runs in O(1) in max-heap vs O(lgN) in BST (in case if BST is balanced),
insertion and deletion will take O(lgN) for both max-heap and balanced BST.

I would appreciate your comments.

Thanks!

Kind regards,
Elmira

0 Likes
#2

Hey Elmira,

Thanks for this good question. At first glance, it seems totally reasonable to use max-heap to solve this. However, there is one critical requirement of the algorithm forbids the use of max-heap as we need to delete a line segment according to his height when you encounter a right endpoint. Remember that max-heap can only delete max in O(logN) time but for an arbitrary key, its deletion is O(N) time instead.

From algorithm perspective, BST is the super set of heap because whatever heap can do, BST also can do, and sometimes it does better (e.g., finding an element). Under this situation, there is a good question arose, why we still need heap? This is another great question, and I would like to leave you to think about it as a brain-teaser :wink:

0 Likes
#3

Dear Tsung-Hsien,

Thank you for the great reply!
I really missed that we need to delete arbitrary key from the heap which leads to O(N).
Thank you for pointing this out!

I thought about your proposal to use heap in this task and have the following idea:

  1. create a max-heap and insert all intervals into it
    (as compare function use this approach: standard compare by heights, if equal height - the greater is an interval with smallest left endpoint )
    complexity: O(NlgN)
  2. create empty interval search tree
  3. in a cycle while the max-heap is not empty
    3.1 remove the max interval from the heap and do the following (let’s refer it to as current max interval)
    complexity: O(lgN)
    3.2 search for intersected interval(s) in the interval search tree with current max interval
    complexity: O(R*logN), where R - number of intersected intervals, N - number of all intervals
    3.3 if there are no intersected intervals - > insert current interval to the interval search tree and continue to the cycle
    complexity: O(lgN)
    3.4. if there are several intersected intervals ->
    3.4.1 split current max-interval to several intervals such that they should not intersect with returned intervals from the interval search tree
    i hung with this sub-task: just for now have only one idea:
    start process from the lowest tree interval or current max interval
    any left endpoint of tree interval may be an end of new interval, and any right endpoint of tree interval - start of new interval
    complexity: O® for the subtask, where R - number of intersected intervals ?
    3.4.2 insert new intervals to the interval search tree
    complexity: O(lgR)
  4. as a result all required intervals will be placed in the interval search tree.
    In-order tree traversal will return required result.

If I’m not wrong, the total complexity is O(NlogN), but I’m not sure.

For interval search tree we can use red-black tree with left endpoint as a key, and max value as a max right endpoint of a tree rooted at that node.

Please let me know if I’m going in the right direction or not.

Thank you in advance!

Elmira

0 Likes
#4

Hey Elmira,

I haven’t checked your algorithm very carefully but I do have one question for you is that since interval search tree (which is interval tree https://en.wikipedia.org/wiki/Interval_tree I guess) is mostly an augmented BST. So I think there is little reason to use both heap and BST for solving this problem under the condition that a simple BST could serve the purpose.

0 Likes
#5

Hi Tsung-Hsien,

yes, exactly augmented BST for fastest intervals intersections finding,
as a result augmented BST will contain all result intervals.

Elmira

0 Likes
#6

Hey Elmira,

As I asked before, I see no reason to use augmented BST + max-heap to solve a problem that can be solved in BST with identical time complexity. BTW, it is really good to see you know how to apply interval tree to solve this problem and you actually have a solid algorithm knowledge for sure. Please let me know if you have any other problem.

0 Likes
#7

Hi Tsung-Hsien,

Yes, I completely agree with you that there is no reason to use augmented BST (that was just a not good attempt to solve the task with max-heap).

Thank you for your feedback!

Elmira

0 Likes