使用数组插入时间为 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) 线性搜索以查找删除，移动剩余的元素数组向下一位。

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

Answer 2

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

这是在内部使用 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
    }
}

Answer 3

未排序的链表听起来像是符合规定的要求（尽管对于大多数实际应用来说它们似乎有点愚蠢）。您有恒定的插入时间（将其粘贴在末尾或开头）和线性删除时间（扫描列表中的最小元素）。

Answer 4

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

以下是实现这一目标的方法。

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

通过这样做，您的优先级队列插入时间为 O(1)，并且删除方法具有 O(N) 时间。

Answer 5

没有办法实现 O(1) 插入方法并使数组保持排序。如果您将排序传递给删除方法，您可以做的最快的事情是 O(N log(n)) 快速排序或其他方法。
或者您可以像 LBushkin 建议的那样在插入方法中执行 O(log n) 算法。