Очередь приоритетов с O (1) Время вставки с использованием массивов?

Question

Мой код сейчас имеет время вставки O (N) и время удаления O (1).Мне нужно изменить это вокруг. Я пытаюсь реализовать время вставки O (1) и время удаления O (N).

Легенда:

nItems = количество предметов / объектов.Первоначально установлено значение 0.

queArray - это мой массив длинных целых чисел.

Вот мои два метода.Метод вставки выполняет всю работу по сортировке.Удалите метод только одной строкой - чтобы удалить первый элемент в массиве, который оказывается наименьшим числом благодаря нашему методу вставки.

Если бы я изменил время вставки на 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

Чтобы изменить время вставки на 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 4

Несортированный связанный список звучит так, как будто он соответствует заявленным требованиям (хотя они кажутся немного глупыми для большинства практических приложений).У вас есть постоянное время вставки (вставьте его в конец или начало) и линейное время удаления (отсканируйте список на предмет наименьшего элемента).

Answer 5

Нет способа реализовать метод вставки O (1) и сохранить ваш массив отсортированным. Если вы передадите свою сортировку методу удаления, вы можете быстро набрать O (N log (n)) с быстрой сортировкой или что-то еще. Или вы можете сделать алгоритм O (log n) в методе вставки, как предлагает Л.Бушкин.