I do this by having items implement the provided IPrioritizable interface. I was initially going to build it on the INotifyPropertyChanged interface but I thought this solution was simpler. The interface has 2 methods to Add/Remove an Action that notifies the PriorityQueue that it needs to be sorted. It now also requires a IComparer be provided. An example of this would be:
Whilst not as simple as it's predecessor it wastes less time ordering the queue on sequential pops.