كيفية القيام فعالة التحديث الأولوية في المحكمة الخاصة بلبنان priority_queue?

Question

لدي priority_queue من بعض وجوه:

typedef priority_queue<Object> Queue;
Queue queue;

من وقت لآخر ، أولوية واحدة من الأشياء قد تتغير - لا تحتاج إلى أن تكون قادرا على تحديث أولوية هذا الكائن في طابور بطريقة فعالة.حاليا أنا أستخدم هذه الطريقة التي يعمل لكن يبدو غير فعال:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

أنا تنفيذه بهذه الطريقة لأنني كنت في عجلة من أمرك في ذلك الوقت وهذا كان أسرع شيء يمكن أن أفعله أنني يمكن أن يكون متأكد موافق.يجب أن يكون هناك طريقة أفضل من هذا على الرغم من.حقا ما أريده هو طريقة إما:

• استخراج سبيل المثال مع تغير أولوية إدراج واحدة جديدة مع أولوية جديدة قيمة
• تحديث سبيل المثال مع تغير الأولويات ومن ثم تحديث قائمة الانتظار بحيث يتم فرز بشكل صحيح

ما هي أفضل طريقة للقيام بذلك ؟

Answer 1

أعتقد أنك لم يحالفك الحظ في قائمة انتظار الأولوية القياسية لأنه لا يمكنك الوصول إلى القائمة الأساسية/المتجه/القائمة أو أي شيء آخر.أنت بحاجة إلى تنفيذ ما تريده بنفسك - فالأمر ليس بهذه الصعوبة.

Answer 2

يمكنني اقتراح خيارين لحل المشكلة، على الرغم من عدم قيام أي منهما بإجراء تحديث حقيقي.

1. استخدم ال priority_queue وادفع العنصر في كل مرة ترغب في تحديثه.تقبل حقيقة أنه سيكون لديك إدخالات عديمة الفائدة في قائمة الانتظار.عند ظهور القيمة العليا، تحقق مما إذا كانت تحتوي على القيمة المحدثة.إذا لم يكن الأمر كذلك، تجاهله وافتح التالي.

   بهذه الطريقة يمكنك تأخير إزالة العنصر المحدث حتى يصل إلى الأعلى.لقد لاحظت أن هذا النهج يستخدمه كبار المبرمجين الذين يقومون بتنفيذ خوارزمية Dijkstra.

2. يستخدم set.يتم فرزها أيضًا حتى تتمكن من استخراج العنصر الأكبر في الوقت اللوغاريتمي.يمكنك أيضًا إزالة العنصر القديم قبل إدراجه مرة أخرى.لذلك لا توجد حتى الآن عملية تحديث ممكنة، ولكن الإزالة وإعادة الإدخال ممكنة.

يبدو أن تعقيد كلا النهجين هو نفسه.

Answer 3

الطريقة الأكثر مباشرة للقيام بذلك باستخدام STL (التي أعرفها) هي إزالة الإدخال وتحديث أولويته ثم إعادة إدراجه.يعد القيام بذلك بطيئًا جدًا باستخدام std::priority_queue، ولكن يمكنك القيام بنفس الشيء باستخدام std::set.لسوء الحظ عليك أن تكون حريصًا على عدم تغيير أولوية الكائن عندما يكون في المجموعة.

لقد قمت بتنفيذ فئة mutable_priority_queue القائمة على اللصق معًا std::multimap (لأولوية تعيين القيمة) وstd::map (لقيمة تعيين الأولوية) الذي يسمح لك بإدراج/إزالة العناصر بالإضافة إلى تحديث القيم الموجودة في اللوغاريتمي وقت.يمكنك الحصول على الكود ومثال لكيفية استخدامه هنا

Answer 4

البيانات المناسبة هيكل يسمى "فيبوناتشي كومة".ولكن تحتاج إلى تنفيذ ذلك بنفسك.إدراج/التحديثات O(1) ExtractMin O(logn)

Answer 5

لقد قمت بتنفيذ قائمة انتظار ذات أولوية عالية الأداء وقابلة للتحديث وجعلتها متاحة على جيثب.

هذه هي الطريقة التي تستخدمها عادةً:

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

لاستكمال إجابة جاركزيك، إذا كان كلاهما بالفعل set وأساليب "الكومة النقية ذات الإدخالات غير المفيدة" لها نفس التعقيد stl::set عادةً ما يكون أداء الإصدار أبطأ بكثير من الإصدار stl::priority_queue نظرًا لأنه يتم تنفيذه باستخدام أشجار ذات لون أحمر وأسود والتي تضمن فقط أن يكون عمقها أقل من 2*log_2(n_elements) وتتطلب تحديثات منتظمة، بينما stl::priority_queue هي كومة ثنائية نقية وسريعة قدر الإمكان.ولهذا السبب يتم استخدامه عادةً عند تنفيذ Dijkstra.

ومع ذلك، قد يكون النهج المحدد أسرع عند إجراء الكثير من التحديثات على عدد قليل من العقد الأساسية.وهذا أيضًا هو المكان الذي سيؤدي فيه استخدام مكتبتي إلى تحقيق أكبر قدر من التحسن.

Answer 6

قد ترغب في إلقاء نظرة على replace_if مع مثال هنا.

Answer 7

لسوء الحظ لا يمكنك تحديث القيمة في Priority_queue.لا يقدم Priority_queue مثل هذه الواجهة.

أعتقد أنه من الأفضل أن تستخدمه set كما قال جاركزيك أو استخدمه هذا الحل(باستخدام make_heap).