Given your link, you seem to be interested in data structures supporting the following operations:
- Create(m): create a new instance with room for m elements.
- Size(): return the number of elements currently stored in the instance.
- Insert(k): insert an element with priority k.
- ExtractMax(): return the maximal priority currently stored, and remove it.
Since Size() is easy to implement in constant time as part of the other operations, I will not discuss it below.
Here are three sample implementations:
Unsorted array:
- Create() simply allocates memory.
- Insert() simply inserts the element at position i+1, where i is the current number of elements.
- ExtractMax() goes over the entire array, finding the maximum; and then "compacts" the array by moving all elements to the right of the maximum one entry to the left.
Sorted array: (your implementation)
- Create() simply allocates memory.
- Insert() first scans the array to find the proper location for the element, then moves all elements to the right of the intended location one entry to the right, and finally stores the element.
- ExtractMax() returns and removes the ith element, where i is the number of elements currently in the instance.
Binary heap:
- Create() simply allocates memory.
- Insert() and ExtractMax() are described on Wikipedia.
Binary heaps are implemented using "partially sorted" arrays. That is, the order of elements in the array is not arbitrary, but it is also not completely determined. Rather, we are only guaranteed that A[i] ≥ A[2i],A[2i+1]. This freedom allows us to trade-off the running time of the two operations Insert() and ExtractMax().
In all of these implementations, Create() is roughly the same, so to compare the various implementations it suffices to consider the two operations Insert() and ExtractMax():
$$
\begin{array}{c|c|c}
\text{Implementation} & \text{Insert()} & \text{ExtractMax()} \\\hline
\text{Unsorted array} & O(1) & O(n) \\
\text{Sorted array} & O(n) & O(1) \\
\text{Binary heap} & O(\log n) & O(\log n)
\end{array}
$$
Here $n$ is the number of elements currently in the array.
If you perform many Insert() and ExtractMax() operations, a binary heap is likely to be more efficient.
Another operation which you mentioned is
- Initialize(A): add to an empty instance the elements in A
You can add support to this operation to all different implementations mentioned above:
- Unsorted array: simply copy A to the array. Running time: $O(|A|)$.
- Sorted array: copy A and sort the resulting array. Running time: $O(|A|\log|A|)$.
- Binary heap: run Insert() for each element of A. Running time: $O(|A|\log|A|)$.
Considering this operation doesn't strengthen the case of your implementation.
pq = (Key[]) (new Comparable[capacity]);
for create the priority so O(N), and after that you will need insert the n in a O(LogN) element so if you have a fixed list to elements to create a priority queue the cost is the same O(NLogN) $\endgroup$ – Tlaloc-ES Sep 2 '19 at 22:46