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.
Yes you should use priority_queue.It will automatically handle the structure of the heap.
A priority queue is (usually) implemented as a heap.