Question

In a discrete event simulation, a physical system, such as a galaxy or solar system, is modeled as it changes over time based on simulated forces. The objects being modeled define events that are scheduled to occur in the future. Each event, e, is associated with a time, te,in the future. To move the simulation forward,the event,e,that has smallest time,te,in the future needs to be processed. To process such an event, e is removed from the set of pending events, and a set of physical forces are calculated for this event, which can optionally create a constant number of new events for the future, each with its own event time. Describe a way to support event processing in a discrete event simulation in O(logn) time, where n is the number of events in the system.

Answer 1

Given Scenario :

Here, we have a set of events for their future times 'te'. In each step, we need to extract the event with minimum 'te' and proceed with that event and also add other finite numbers of events associated with our extracted event.

One possible approach to do this may be to find the minimum 'te' event in each step. But it will be an O(n) operation in each step.

The optimal solution is to use priority queues. Let us make a min-priority queue of our event 'te' times. A min priority queue is a queue in which the minimum element is at the front of the queue. In this way, we have to just extract the first element of the queue in each step and we are done.

Let us analyze the complexity of the solution:

In a priority queue:

Insertion -> log(n)

So, when a new element is added to the queue, it will take log(n) time to insert it.

Accessing the front element -> O(1).

it just need to access the first element of the queue which is O(1).

So, it maintain a min-priority queue. In each step, access the first element of the queue. Add the new elements in the priority queue.

Minimum priority queues can be easily implemented using minimum heap.

Pseudo Code:

#Function called by min-heap function to buold the heap.

def min_heapify (Arr[ ] , i, N)

left  = 2*i;
right = 2*i+1;
smallest;
if left <= N and Arr[left] < Arr[ i ] 
     smallest = left
else
    smallest = i
END If

if right <= N and Arr[right] < Arr[smallest] 
    smallest = right
END If
if smallest != i

    swap (Arr[ i ], Arr[ smallest ])
    min_heapify (Arr, smallest,N)
END If 

End

#function to build min-heap

def min-heap(Arr[], N)

i = N/2
for i : N/2 to 1 in steps of 1 
    min_heapify (Arr, i);

End

# function to extract minimum time

def min_extract( A[ ] )

return A [ 0 ]

END

#functions to insert new elements

def insertion (Arr[ ], value)

    length = length + 1
    Arr[ length ] = -1 
    value_increase (Arr, length, val)
END

def value_increase(Arr [ ], length, val)

if val < Arr[ i ]
        return
    END If
    Arr[ i ] = val;
    while i > 1 and Arr[ i/2 ] < Arr[ i ]
    
        swap|(Arr[ i/2 ], Arr[ i ]);
        i = i/2;
    END While

END