C Queue # ưu tiên

Question

Tôi đang tìm kiếm một hàng đợi ưu tiên với một giao diện như thế này:

class PriorityQueue<T> 
{ 
    public void Enqueue(T item, int priority) 
    { 
    } 

    public T Dequeue() 
    { 
    } 
} 

Tất cả việc triển khai Tôi đã nhìn thấy rằng item là một IComparable nhưng tôi không thích cách tiếp cận này; Tôi muốn chỉ định mức độ ưu tiên khi tôi đẩy nó lên hàng đợi.

Nếu triển khai sẵn sàng thực hiện không tồn tại, cách tốt nhất để tự mình thực hiện việc này là gì? Tôi nên sử dụng cấu trúc dữ liệu cơ bản nào? Một số loại cây tự cân bằng, hoặc cái gì? Cấu trúc C# .net chuẩn sẽ rất đẹp.

Answer 1

Nếu bạn có một thực hiện hàng đợi ưu tiên hiện tại dựa trên IComparable, bạn có thể dễ dàng sử dụng để xây dựng cấu trúc bạn cần:

public class CustomPriorityQueue<T> // where T need NOT be IComparable 
{ 
    private class PriorityQueueItem : IComparable<PriorityQueueItem> 
    { 
    private readonly T _item; 
    private readonly int _priority: 

    // obvious constructor, CompareTo implementation and Item accessor 
    } 

    // the existing PQ implementation where the item *does* need to be IComparable 
    private readonly PriorityQueue<PriorityQueueItem> _inner = new PriorityQueue<PriorityQueueItem>(); 

    public void Enqueue(T item, int priority) 
    { 
    _inner.Enqueue(new PriorityQueueItem(item, priority)); 
    } 

    public T Dequeue() 
    { 
    return _inner.Dequeue().Item; 
    } 
} 

Answer 2

Có vẻ như bạn có thể cuộn của riêng mình với một seriews của hàng đợi, một cho mỗi ưu tiên. Từ điển và chỉ cần thêm nó vào thích hợp.

Answer 3

Bạn có thể thêm kiểm tra an toàn và những gì không, nhưng đây là một thực hiện rất đơn giản sử dụng SortedList:

class PriorityQueue<T> { 
    SortedList<Pair<int>, T> _list; 
    int count; 

    public PriorityQueue() { 
     _list = new SortedList<Pair<int>, T>(new PairComparer<int>()); 
    } 

    public void Enqueue(T item, int priority) { 
     _list.Add(new Pair<int>(priority, count), item); 
     count++; 
    } 

    public T Dequeue() { 
     T item = _list[_list.Keys[0]]; 
     _list.RemoveAt(0); 
     return item; 
    } 
} 

Tôi giả định rằng giá trị nhỏ hơn của priority tương ứng với các mặt hàng ưu tiên cao hơn (điều này rất dễ dàng để sửa đổi).

Nếu có nhiều chủ đề sẽ truy cập vào hàng đợi, bạn cũng sẽ cần thêm cơ chế khóa. Điều này thật dễ dàng, nhưng hãy cho tôi biết nếu bạn cần hướng dẫn tại đây.

SortedList được triển khai bên trong dưới dạng cây nhị phân.

Việc triển khai ở trên cần các lớp trợ giúp sau. Địa chỉ này nhận xét của Lasse V. Karlsen rằng các mục có cùng mức độ ưu tiên không thể được thêm vào bằng cách sử dụng triển khai ngây thơ bằng cách sử dụng SortedList.

class Pair<T> { 
    public T First { get; private set; } 
    public T Second { get; private set; } 

    public Pair(T first, T second) { 
     First = first; 
     Second = second; 
    } 

    public override int GetHashCode() { 
     return First.GetHashCode()^Second.GetHashCode(); 
    } 

    public override bool Equals(object other) { 
     Pair<T> pair = other as Pair<T>; 
     if (pair == null) { 
      return false; 
     } 
     return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second)); 
    } 
} 

class PairComparer<T> : IComparer<Pair<T>> where T : IComparable { 
    public int Compare(Pair<T> x, Pair<T> y) { 
     if (x.First.CompareTo(y.First) < 0) { 
      return -1; 
     } 
     else if (x.First.CompareTo(y.First) > 0) { 
      return 1; 
     } 
     else { 
      return x.Second.CompareTo(y.Second); 
     } 
    } 
} 

Answer 4

Bạn có thể viết một wrapper xung quanh một trong những triển khai hiện có mà sửa đổi giao diện theo sở thích của bạn:

using System; 

class PriorityQueueThatYouDontLike<T> where T: IComparable<T> 
{ 
    public void Enqueue(T item) { throw new NotImplementedException(); } 
    public T Dequeue() { throw new NotImplementedException(); } 
} 

class PriorityQueue<T> 
{ 
    class ItemWithPriority : IComparable<ItemWithPriority> 
    { 
     public ItemWithPriority(T t, int priority) 
     { 
      Item = t; 
      Priority = priority; 
     } 

     public T Item {get; private set;} 
     public int Priority {get; private set;} 

     public int CompareTo(ItemWithPriority other) 
     { 
      return Priority.CompareTo(other.Priority); 
     } 
    } 

    PriorityQueueThatYouDontLike<ItemWithPriority> q = new PriorityQueueThatYouDontLike<ItemWithPriority>(); 

    public void Enqueue(T item, int priority) 
    { 
     q.Enqueue(new ItemWithPriority(item, priority)); 
    } 

    public T Dequeue() 
    { 
     return q.Dequeue().Item; 
    } 
} 

Điều này cũng giống như đề nghị của itowlson. Tôi chỉ mất nhiều thời gian hơn để viết cho tôi vì tôi đã điền vào nhiều phương pháp. : -s

Answer 5

Đây là một triển khai nhẹ rất đơn giản có hiệu suất O (log (n)) cho cả push và pop. Nó sử dụng một heap data structure được xây dựng trên đầu trang của một Danh sách <T>.

/// <summary>Implements a priority queue of T, where T has an ordering.</summary> 
/// Elements may be added to the queue in any order, but when we pull 
/// elements out of the queue, they will be returned in 'ascending' order. 
/// Adding new elements into the queue may be done at any time, so this is 
/// useful to implement a dynamically growing and shrinking queue. Both adding 
/// an element and removing the first element are log(N) operations. 
/// 
/// The queue is implemented using a priority-heap data structure. For more 
/// details on this elegant and simple data structure see "Programming Pearls" 
/// in our library. The tree is implemented atop a list, where 2N and 2N+1 are 
/// the child nodes of node N. The tree is balanced and left-aligned so there 
/// are no 'holes' in this list. 
/// <typeparam name="T">Type T, should implement IComparable[T];</typeparam> 
public class PriorityQueue<T> where T : IComparable<T> { 
    /// <summary>Clear all the elements from the priority queue</summary> 
    public void Clear() { 
     mA.Clear(); 
    } 

    /// <summary>Add an element to the priority queue - O(log(n)) time operation.</summary> 
    /// <param name="item">The item to be added to the queue</param> 
    public void Add (T item) { 
     // We add the item to the end of the list (at the bottom of the 
     // tree). Then, the heap-property could be violated between this element 
     // and it's parent. If this is the case, we swap this element with the 
     // parent (a safe operation to do since the element is known to be less 
     // than it's parent). Now the element move one level up the tree. We repeat 
     // this test with the element and it's new parent. The element, if lesser 
     // than everybody else in the tree will eventually bubble all the way up 
     // to the root of the tree (or the head of the list). It is easy to see 
     // this will take log(N) time, since we are working with a balanced binary 
     // tree. 
     int n = mA.Count; mA.Add (item); 
     while (n != 0) { 
     int p = n/2; // This is the 'parent' of this item 
     if (mA[n].CompareTo (mA[p]) >= 0) break; // Item >= parent 
     T tmp = mA[n]; mA[n] = mA[p]; mA[p] = tmp; // Swap item and parent 
     n = p;   // And continue 
     } 
    } 

    /// <summary>Returns the number of elements in the queue.</summary> 
    public int Count { 
     get { return mA.Count; } 
    } 

    /// <summary>Returns true if the queue is empty.</summary> 
    /// Trying to call Peek() or Next() on an empty queue will throw an exception. 
    /// Check using Empty first before calling these methods. 
    public bool Empty { 
     get { return mA.Count == 0; } 
    } 

    /// <summary>Allows you to look at the first element waiting in the queue, without removing it.</summary> 
    /// This element will be the one that will be returned if you subsequently call Next(). 
    public T Peek() { 
     return mA[0]; 
    } 

    /// <summary>Removes and returns the first element from the queue (least element)</summary> 
    /// <returns>The first element in the queue, in ascending order.</returns> 
    public T Next() { 
     // The element to return is of course the first element in the array, 
     // or the root of the tree. However, this will leave a 'hole' there. We 
     // fill up this hole with the last element from the array. This will 
     // break the heap property. So we bubble the element downwards by swapping 
     // it with it's lower child until it reaches it's correct level. The lower 
     // child (one of the orignal elements with index 1 or 2) will now be at the 
     // head of the queue (root of the tree). 
     T val = mA[0]; 
     int nMax = mA.Count - 1; 
     mA[0] = mA[nMax]; mA.RemoveAt (nMax); // Move the last element to the top 

     int p = 0; 
     while (true) { 
     // c is the child we want to swap with. If there 
     // is no child at all, then the heap is balanced 
     int c = p * 2; if (c >= nMax) break; 

     // If the second child is smaller than the first, that's the one 
     // we want to swap with this parent. 
     if (c + 1 < nMax && mA[c + 1].CompareTo (mA[c]) < 0) c++; 
     // If the parent is already smaller than this smaller child, then 
     // we are done 
     if (mA[p].CompareTo (mA[c]) <= 0) break; 

     // Othewise, swap parent and child, and follow down the parent 
     T tmp = mA[p]; mA[p] = mA[c]; mA[c] = tmp; 
     p = c; 
     } 
     return val; 
    } 

    /// <summary>The List we use for implementation.</summary> 
    List<T> mA = new List<T>(); 
} 

Answer 6

Điều gì sẽ khủng khiếp như thế này?

class PriorityQueue<TItem, TPriority> where TPriority : IComparable 
{ 
    private SortedList<TPriority, Queue<TItem>> pq = new SortedList<TPriority, Queue<TItem>>(); 
    public int Count { get; private set; } 

    public void Enqueue(TItem item, TPriority priority) 
    { 
     ++Count; 
     if (!pq.ContainsKey(priority)) pq[priority] = new Queue<TItem>(); 
     pq[priority].Enqueue(item); 
    } 

    public TItem Dequeue() 
    { 
     --Count; 
     var queue = pq.ElementAt(0).Value; 
     if (queue.Count == 1) pq.RemoveAt(0); 
     return queue.Dequeue(); 
    } 
} 

class PriorityQueue<TItem> : PriorityQueue<TItem, int> { } 

Answer 7

Tôi nhận ra rằng câu hỏi của bạn đặc biệt yêu cầu một việc thực hiện phi IComparable-based, nhưng tôi muốn chỉ ra một bài báo gần đây từ Visual Studio Magazine.

http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx

Bài viết này với @ của itowlson thể đưa ra một câu trả lời hoàn chỉnh.

Answer 8

Đó là giao diện chính xác được sử dụng bởi highly optimized C# priority-queue của tôi.

Nó được phát triển đặc biệt cho các ứng dụng đường dẫn (A *, v.v.), nhưng cũng nên hoạt động hoàn hảo cho bất kỳ ứng dụng nào khác.

Vấn đề duy nhất có thể là, để ép ra hiệu suất tối đa tuyệt đối, việc triển khai yêu cầu các giá trị được enqueued để mở rộng PriorityQueueNode.

public class User : PriorityQueueNode 
{ 
    public string Name { get; private set; } 
    public User(string name) 
    { 
     Name = name; 
    } 
} 

... 

HeapPriorityQueue<User> priorityQueue = new HeapPriorityQueue<User>(MAX_USERS_IN_QUEUE); 
priorityQueue.Enqueue(new User("Jason"), 1); 
priorityQueue.Enqueue(new User("Joseph"), 10); 

//Because it's a min-priority queue, the following line will return "Jason" 
User user = priorityQueue.Dequeue(); 

Answer 9

Một chút muộn nhưng tôi sẽ thêm nó vào đây để tham khảo

https://github.com/ERufian/Algs4-CSharp

khóa-giá trị cặp hàng đợi ưu tiên được thực hiện trong Algs4/IndexMaxPQ.cs, Algs4/IndexMinPQ.cs và Algs4/IndexPQDictionary.cs

Ghi chú:

1. Nếu ưu tiên không phải là IComparable' s, một IComparer có thể được xác định trong hàm dựng
2. Thay vì enqueueing đối tượng và ưu tiên của nó, những gì enqueued là một chỉ mục và ưu tiên của nó (và, cho câu hỏi ban đầu, một danh sách riêng biệt hoặc T [] sẽ là cần thiết để chuyển đổi chỉ mục đó thành kết quả mong đợi)