How to improve the priority queues further
Try to keep the active part of the queue in the cache.
The active set for deletemin operations is the set of smaller elements.
For insertion we can keep a buffer. So, that when we flush the buffer, it is in batch mode. This improves the cache performance.