Simple Priority Queue
[This answer comes a couple of years after the question was posted. The Community User keeps bumping the question because there is an answer without upvotes, not worth up-voting. It also has 2k+ views. So maybe a good review is in order.]

This priority queue implementation has an \$O(1)\$ push operation, and an \$O(n)\$ pop operation, but with \$n\$ being the size of the container (500) rather than the number of elements in the queue. However, the push complexity increases once there have been 500 elements in the queue, because the two data arrays will be reallocated when pushing more elements. Note that this is not 500 elements currently in the queue, but 500 elements having gone through the queue. Used array elements are not re-used.

Code review:

Variable names are excellent: it is clear what they mean without any comments.

The class has no documentation. Documentation on how to use a class or a function is as important (IMO) as the code working correctly.

There are a few statements that could be more concise: NaN*ones(500,1) is the same as NaN(500,1). thePQueue.valueList{500} = [] is better written as thePQueue.valueList = cell(1,500). thePQueue.nElements is set to 0 twice in the constructor.

The constructor PQ2() could take an optional input argument specifying how many elements one expects will go through the queue, to give the queue an appropriate initial size.

Timing:

This is a very fast implementation of a priority queue (as long as it is not used for too long, because performance degrades after 500 elements have been pushed. I wrote the following script to time it, and try to improve on it:

t_push = 0;
t_pop = 0;
for jj=1:100
   pq = PQ2;
   tic;
   for ii=1:500
      pq.push(ii,randi(10000));
   end
   t_push = t_push + toc;
   tic;
   for ii=1:500
      pq.pop;
   end
   t_pop = t_pop + toc;
end
t_push
t_pop


Sure, it's a little simplistic, but so be it. It pushes 500 elements, then pops 500 elements. This is repeated, with a fresh queue, 100 times. The OP's priority queue implementation gives me t_push = 0.1822 and t_pop = 0.2930. I could not make this significantly faster.

I compared this against the classical \$O(\log n)\$ priority queue as implemented in the link provided by the OP. That one gave t_push = 5.9049 and t_pop = 28.1718. No wonder OP thinks it's slow. That implementation has many problems, one is that it tries to do memory management. If we let MATLAB do the memory management (MATLAB will double the storage when appending elements to an array, and does so much more efficiently than this user's code), and store the priorities in a numeric array rather than a cell array, I get t_push = 0.5715 and t_pop = 1.8866, 10 times faster for pushing and 15 times faster for popping. But still nowhere near the speed of the code in this question.

Next, I increased the size of the queue to 5000, and changed the test code to run 10 iterations of pushing and popping 5000 elements. Push times remained similar for both queues, and pop times increased to 0.9861 for OP's code, and 2.8028 for the other implementation. Here one can see the \$O(n)\$ vs \$O(\log n)\$ characteristic of these two implementations. But it is clear that n times a small number is much less than log(n) times a large number.

For very large queues, with millions of elements, I'd stick to one of the other solutions proposed in the Stack Overflow question (the built-in Java queue or a C++ MEX-file implementation).