Problem:
The priority queue is built on a max/min heap. The routines along with max/min heap are defined in mheap.h.
The bug is with mheap.h.
After each insertion into the max/min heap, the insertion function fails to heapify the heap accordingly. This yields undeterminstic behaviors. 

Fix:
Calling the heapify() in mheap.h does not help to solve the problem.
You may need to either fix the insertion function by yourself or by calling the initialize function comes with mheap.h. 
Note that the latter case is a simple fix but it will give you overheads.