Both the Insert and the Extract-Min operations have a running time of O(log n). There are n tasks and each task has to be inserted to the heap and later extracted from the heap, resulting in a running time of O(n log n).
The reason Insert has a running time of O(log n) is that when inserting we first add the new task to the heap final position. This does not necessarily maintain the heap property, as the priotiy of the new task might be better (having a smaller key) than the priority of its parent. This is why the Insert operation involves the Heapify-Up procedure whose purpose is to restore the heap order. The Heapify-Up procedure has a running time of O(log n).
The reason Extract-Min has a running time of O(log n) is that in the Extract-Min operation we first delete the root of the heap (the first task) and then move the last task to the first position (that is, replacing the root with the task residing in the last position). As this possibly violates the heap property, the Extract-Min involves the execution of the Heapify-Down procedure. The Heapify-Down procedure also has a running time of O(log n).
Non-preemptive sjf can be done in O(nlogn) time complexity using segment tree. Take the inputs of processes in struct and sort the struct array according to arrival time. Now, we will use segment tree to find the range minimum burst time and corresponding process id which will take 2*logn for query and update both.
