使用数组的O(1)插入时间的优先级队列？

Question

我的代码现在有O(N)插入时间和O(1)删除时间.我需要改变这个.我试图实现O(1)插入时间和O(N)删除时间.

传说:

nItems =项目/对象的数量.最初设置为0.

queArray是我的长整数数组.

这是我的两种方法.插入方法完成所有排序工作.删除方法只需一行 - 由于我们的Insert方法,删除数组中第一个恰好是最小数字的元素.

如果我要将插入时间更改为O(1),我是否需要提供"排序任务"来删除方法？毕竟它是一个优先级队列,我们​​必须对它进行排序,否则它将只是一个随机顺序的数字的常规队列.

拜托,任何帮助都会很好!!!

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

如果你想要O(1)插入时间和O(N)移除时间,只需将未分类的新元素添加到内部数组的末尾,并在列表中进行O(N)线性搜索以进行删除,移动其余部分.排列一个.

或者为了更好的实现,您可能需要考虑Fibonacci堆.