1.2. Use Case: Air Traffic Control

So, to motivate search trees let us consider the following example. So, supposing you are an air traffic controller and you controlling access to a single runway, flights have to land and take off. So, the air traffic control tower receives requests from the aircraft about the expected arrival and departure times and these requests come at random times. So, it is not that they come in order of the time of the actual event.

In this example, the scenario is set in an air traffic control tower where the controller manages the landing and takeoff of flights. The unique challenge faced by the controller is that requests arrive in a random order rather than a chronological one. For instance, a request for a landing at 16:23 might come after a takeoff request at 16:12. This disorder creates a need for an efficient management system to ensure that the right decisions are made at the right times.

Imagine a busy restaurant where customers keep sending in their orders at different times. If the chef doesn't have a system to prioritize based on the order of arrival, they might serve food out of sequence, leading to chaos.

So, this is a priority queue, each request goes into the queue, but it has a priority depending on the expected time that it is going to take place. So, we could give a min heap representation and if you take the 6 requests in the order that they come we insert them into the min heap, then we will get the min heap that we see on the right hand side.

A priority queue is used as it allows requests to be processed based on their urgency. In this case, the requests are represented in a min heap, where the request with the earliest expected time gets the highest priority and rises to the top of the heap. By organizing requests this way, the controller can efficiently determine which flight to process next based on its landing or takeoff time.

Think of a hospital emergency room where patients are treated based on the severity of their conditions. The most urgent cases are treated first, much like a min heap prioritizing requests by their earliest scheduled times.

Suppose we have an extra requirement on this, not only do we want to give priority to the earliest event to happen, but we also want to impose some minimum separation of planes to avoid any possibility of collisions on the runway.

In addition to prioritizing the earliest requests, air traffic control must ensure safety by maintaining a minimum separation between aircraft. For instance, if landing or takeoff requests are too close together (less than 3 minutes apart), the controller needs to deny the request or suggest an alternative time to prevent potential collisions.

Consider driving on a highway where there are speed limits and certain distances that cars must maintain from each other. If a driver approaches another car too closely, they may be advised to slow down or change lanes to ensure safety, simulating the air traffic controller's decisions.

Unfortunately, in the heap data structure there is no easy way to do this. So, when 16:55 is added to the heap, we have to scan it against all the elements in the heap in order to find out whether it is within 3 minutes of any of them. So, this would be a linear scan.

The limitation of using heaps arises because, although insertion and deletion are efficient operations, checking constraints like time separation requires scanning through all existing requests. This linear scan to ensure the safety requirement complicates the heap's efficiency since it potentially adds significant time to operations.

Imagine a teacher reviewing all students' test times to ensure no one is too close to another. If there are too many students, checking each student's schedule can take a long time, just as scanning a heap can be time-consuming.

If you look at 16:18 for example, then the next smaller value is here, so this is the predecessor 16:12 and the next bigger value is here, so this is the successor.

To manage time constraints efficiently, the idea of predecessor and successor values becomes important. Identifying the nearest preceding value (predecessor) and succeeding value (successor) helps determine if the new request meets the required time separations. This is crucial for ensuring safety on the runway, as it allows for quick comparisons with adjacent flight times.

This is like a librarian organizing books on a shelf. If a new book arrives, the librarian checks where it fits among existing books by finding the closest larger and smaller book titles. This helps ensure the library remains orderly.

--