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

Question

我的代码现在有 O(N) 的插入时间和 O(1) 的删除时间。我需要改变这一点。 我正在尝试实现 O(1) 插入时间和 O(N) 删除时间。

图例:

nItems = 项目/对象的数量。初始设置为 0。

queArray 是我的长整数数组。

这是我的两种方法。插入方法完成所有排序工作。 Delete 方法只有一行 - 由于我们的 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 heap .