Priority Queue with O(1) Insertion Time using Arrays?

Question

My code right now has O(N) insertion time, and O(1) removal time. I need to change this around. I am trying to implement O(1) insertion time and O(N) deletion time.

Legend:

nItems = number of items/objects. Initially is set 0.

queArray is my array of long integers.

Here are my two methods. Insertion method does all the sorting work. Delete method just one line - to delete the first element in the array which happens to be the smallest number thanks to our Insert method.

If I were to change insertion time to O(1) would I need to give "sorting task" to remove method? It's a priority queue after all and we have to sort it, otherwise it would be just a regular queue with numbers in random order.

Please, any help would be nice!!!

public void insert(long item) {
    int j;
    if(nItems==0) // if no items,
        queArray[nItems++] = item; // insert at 0
    else {
        for(j=nItems-1; j>=0; j--) { // start at the end
            if( item > queArray[j] ) // if new item larger,
                queArray[j+1] = queArray[j]; // shift upward
            else // if smaller,
                break; // done shifting
        } // end for

        queArray[j+1] = item; // insert it
        nItems++;
    } // end else (nItems > 0)
} 

public long remove() // remove minimum item
{ return queArray[--nItems]; }

Answer 1

If you want O(1) insertion time and O(N) removal time, simply add new elements unsorted to the end of your internal array, and do an O(N) linear search through your list for removals, shifting the rest of the array down one.

Or for a better implementation, you may want to consider a Fibonacci heap.