Priority queue with ubounded number of elements (i.e., with dynamic storage)
I don't understand your claim that a traditional heap is too costly to augment. If the heap is currently of size $N$ and the $N+1$st element is inserted, allocate a new array of size $2N$ and copy the old heap into its prefix. This takes amortized constant time. You can also shrink the heap in this way, for example if it is only half full you can shrink it to two-thirds of its size.