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

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.

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

Legend:

传说:

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

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

queArray is my array of long integers.

queArray是我的长整数数组。

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.

以下是我的两种方法。插入方法完成所有的排序工作。删除方法只有一行——删除数组中的第一个元素，这是由于我们的Insert方法，它是最小的数字。

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.

如果我将插入时间更改为O(1)，是否需要给“排序任务”来删除方法?毕竟它是一个优先队列，我们必须对它进行排序，否则它就是一个有随机数的常规队列。

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]; }

5 个解决方案

#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.

如果您想要O(1)插入时间和O(N)删除时间，只需将未排序的新元素添加到内部数组的末尾，并在列表中进行O(N)线性搜索，将其余的数组向下移动。

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

或者为了更好的实现，您可能需要考虑一个斐波那契堆。

#2

I'm not certain you can achieve O(1) insertion time for an array-based priority queue. You could get O(log n) by using a min/max heap structure.

我不确定您是否可以实现基于数组的优先队列的O(1)插入时间。使用最小堆/最大堆结构可以得到O(log n)。

Here's an implementation of that using a List<> internally (but that could be swapped to an array implementation easily enough.

下面是在内部使用List<>实现的一个实现(但是可以很容易地将其转换为数组实现。

using System;
using System.Collections;
using System.Collections.Generic;

namespace HeapADT
{
    public class Heap<T> : ICollection, IEnumerable<T>
        where T : IComparable<T>
    {
        #region Private Members
        private readonly List<T> m_Items;
        private readonly IComparer<T> m_Comparer;
        #endregion

        #region Constructors
        public Heap()
            : this(0)
        {}

        public Heap( int capacity )
            : this( capacity, null )
        {}

        public Heap( IEnumerable<T> items )
            : this( items, null )
        {}

        public Heap( int capacity, IComparer<T> comparer )
        {
            m_Items = new List<T>(capacity);
            m_Comparer = comparer ?? Comparer<T>.Default;
        }

        public Heap( IEnumerable<T> items, IComparer<T> comparer )
        {
            m_Items = new List<T>(items);
            m_Comparer = comparer ?? Comparer<T>.Default;
            BuildHeap();
        }
        #endregion

        #region Operations
        public void Add( T item )
        {
            m_Items.Add( item );

            var itemIndex = Count - 1;

            while( itemIndex > 0 )
            {
                var parentIndex = ParentIndex(itemIndex);
                // are we a heap? If yes, then we're done...
                if( m_Comparer.Compare( this[parentIndex], this[itemIndex] ) < 0 )
                    return;
                // otherwise, sift the item up the heap by swapping with parent
                Swap( itemIndex, parentIndex );
                itemIndex = parentIndex;
            }
        }

        public T RemoveRoot()
        {
            if( Count == 0 )
                throw new InvalidOperationException("Cannot remove the root of an empty heap.");

            var rootItem = this[0];
            ReplaceRoot(RemoveLast());
            return rootItem;
        }

        public T RemoveLast()
        {
            if( Count == 0 )
                throw new InvalidOperationException("Cannot remove the tail from an empty heap.");

            var leafItem = this[Count - 1];
            m_Items.RemoveAt( Count-1 );
            return leafItem;
        }

        public void ReplaceRoot( T newRoot )
        {
            if (Count == 0)
                return; // cannot replace a nonexistent root

            m_Items[0] = newRoot;
            Heapify(0);
        }

        public T this[int index]
        {
            get { return m_Items[index]; }
            private set { m_Items[index] = value; }
        }
        #endregion

        #region Private Members
        private void Heapify( int parentIndex )
        {
            var leastIndex = parentIndex;
            var leftIndex  = LeftIndex(parentIndex);
            var rightIndex = RightIndex(parentIndex);

            // do we have a right child?
            if (rightIndex < Count) 
                leastIndex = m_Comparer.Compare(this[rightIndex], this[leastIndex]) < 0 ? rightIndex : leastIndex;
            // do we have a left child?
            if (leftIndex < Count) 
                leastIndex = m_Comparer.Compare(this[leftIndex], this[leastIndex]) < 0 ? leftIndex : leastIndex;

            if (leastIndex != parentIndex)
            {
                Swap(leastIndex, parentIndex);
                Heapify(leastIndex);
            }
        }

        private void Swap( int firstIndex, int secondIndex )
        {
            T tempItem = this[secondIndex];
            this[secondIndex] = this[firstIndex];
            this[firstIndex] = tempItem;
        }

        private void BuildHeap()
        {
            for( var index = Count/2; index >= 0; index-- )
                Heapify( index );
        }

        private static int ParentIndex( int childIndex )
        {
            return (childIndex - 1)/2;
        }

        private static int LeftIndex( int parentIndex )
        {
            return parentIndex*2 + 1;
        }

        private static int RightIndex(int parentIndex)
        {
            return parentIndex*2 + 2;
        }
        #endregion
        #region ICollection Members
        public void CopyTo(Array array, int index)
        {
            m_Items.CopyTo( (T[])array, index );
        }

        public int Count
        {
            get { return m_Items.Count; }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return null; }
        }
        #endregion

        #region IEnumerable Members
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public IEnumerator<T> GetEnumerator()
        {
            return m_Items.GetEnumerator();
        }
        #endregion
    }
}

#3

An unsorted linked list sounds like it fits the requirements stated (although they seem a bit silly for most practical applications). You have constant insertion time (stick it at the end or beginning), and linear deletion time (scan the list for the smallest element).

未排序的链表听起来似乎符合所述的需求(尽管对于大多数实际应用程序来说，它们似乎有点傻)。您有常量插入时间(插入到末尾或开始)和线性删除时间(扫描列表中最小的元素)。

#4

In order to change the insertion time to O(1), you can insert elements in to the array unsorted. You can then create a minPeek() method that searches for the smallest key using a linear search and then call that inside the delete/remove method and delete the smallest key.

为了将插入时间更改为O(1)，可以将元素插入到未排序的数组中。然后，您可以创建一个minPeek()方法，使用线性搜索来搜索最小的键，然后在delete/remove方法中调用该方法，并删除最小的键。

Here is how you can achieve this.

以下是你如何做到这一点。

public void insert(int item) {
    queArray[nItems++] = item;
}
public int remove() {
    int removeIndex = minPeek();

    if (nItems - 1 != removeIndex) {

        for (int i = removeIndex; i < nItems - 1; i++) {
            queArray[i] = queArray[i + 1];
        }
    }

    return queArray[--nItems];
}

public int minPeek() {
    int min = 0;

    for (int i = 0; i < maxSize; i++) {
        if (queArray[i] < queArray[min]) {
            min = i;
        }
    }

    return min;
}

By doing so your priority queue has O(1) insertion time and delete method has O(N) time.

这样，您的优先级队列有O(1)插入时间，delete方法有O(N)时间。

#5

There is no way to implement a O(1) insertion method and keep you array sorted. If you pass your sorting to the delete method the fast you can do is a O(N log(n)) with quick sort or something. Or you can do a O(log n) algorithm in the insert method like LBushkin suggest.

没有办法实现O(1)插入方法并保持数组的排序。如果你将你的排序传递给delete方法，你能做的最快的事情就是用一个O(N log(N))来快速排序。或者你可以在insert方法中使用O(log n)算法，比如LBushkin建议。