Priority queue with O (1) Insertion time using arrays?

Question

My code right now has an O (N) input time and an O (1) delete time. I need to change this. I am trying to implement O (1) input time and O (N) delete time.

Legend:

nItems = number of elements / objects. Initially set to 0.

queArray is my array of long integers.

Here are my two methods. The insert method performs all sorting. Delete method only one row - delete the first element in the array, which turned out to be the smallest number thanks to our Insert method.

If I had to change the insertion time to O (1), would I need to give a "sort task" to delete the method? This is a priority queue, and we must sort it, otherwise it will be just another queue with numbers in a random order.

Please any help would be enjoyable.

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

If you want O (1) output time and O (N) deletion time, just add new items unsorted to the end of your internal array and do a linear search of O (N) in your list for deletion, moving the rest of the array down.

Or for a better implementation, you can consider a bunch of Fibonacci .

Answer 2

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

Here's an implementation using List<> inside (but this can easily be replaced with an array implementation.

 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

An unsorted linked list sounds as if it meets the specified requirements (although for most practical applications they seem a little dumb). You have constant insertion time (insert it at the end or beginning) and linear deletion time (view the list for the smallest element).

Answer 4

To change the insertion time to O (1) , you can insert elements into an unsorted array. You can then create a minPeek () method that searches for the smallest key using a linear search, and then calls it inside the delete / delete method and removes the smallest key.

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

So your priority queue has O (1) insertion time and the delete method has O (N) time .

Answer 5

It is not possible to implement the insertion method (1) and save the array sort. If you go through sorting by the delete method, you can quickly execute the O (N log (n)) command with quick sort or something else. Or you can make the O (log n) algorithm in an insert method like LBushkin.