If I solve the IPC Trainers question using heaps as stated, then on popping out the trainer which doesn’t have any lecture remaining and at the very same time maintaining the sort would require the complexity O(n). On the other hand if we just extract him from the heap and heapify using time complexity O(lg n) would disturb the sort. How do i proceed?
This problem will get solved if you use priority queue instead of heaps because in priority queue element at the top would be the one according to which you set the priority which will give you the element in O(1) time.
2 Likes
A priority queue is (usually) implemented as a heap.
2 Likes
@navdha_98, a heap does not maintain any particular sorted order. If you read up on heaps I’m sure the application here will be clearer to you. Good luck!
Yes you should use priority_queue.It will automatically handle the structure of the heap.