An airport is developing a computer simulation of air-traffic control that handl

Question

An airport is developing a computer simulation of air-traffic control that handles events such as landings and takeoffs. Each event has a time-stamp that denotes the time when the event occurs. The simulation program needs to efficiently perform the following two fundamental operations: Insert an event with a given time-stamp (that is, add a future event) Extract the event with smallest time-stamp (that is, determine the next event to process) Which data structure should be used for the above operations? Why? Provide big-oh asymptotic notation for each operation.

Explanation / Answer

Heap data structure can be used in this case. Managing a min heap will help in both operations specially with second. Since removing the root from a min heap gives smallest value in the tree. And after inserting too it will automatically manages the heap. Both operations will have O(logn) complexity.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---