We present Neural Priority Queues, a differentiable analogue to algorithmic priority queues for GNNs. We propose and motivate a desiderata for memory modules, and show that Neural PQs exhibit the desiderata, and reason about their use with algorithmic reasoning. This is further demonstrated by empirical results on the CLRS-30 dataset. Furthermore, we empirically show the effectiveness of Neural PQs with long-range reasoning.