2025-11-17T04:01:13.190278

Retroactive Monotonic Priority Queues via Range Searching

Castro, de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) and partially retroactive priority queues can cost $O(\log m)$ time per operation. So far, it is unknown whether this $O(\log m)$ bound can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue with a cost of $O(\log m + T(m))$ time per operation, where $T(m)$ is the maximum between the query and the update time of a specific range-searching data structure with $m$ elements. Finally, we design a fully retroactive monotonic priority queue that costs $O(\log m \log \log m)$ time per operation.

academic

طوابير الأولويات الرتيبة الاستعادية عبر البحث عن النطاق

المعلومات الأساسية

معرّف الورقة: 2508.09892
العنوان: Retroactive Monotonic Priority Queues via Range Searching
المؤلفون: Lucas Castro, Rosiane de Freitas (معهد الحوسبة - UFAM، البرازيل)
التصنيف: cs.DS (هياكل البيانات والخوارزميات)، cs.CG (الهندسة الحسابية)
وقت النشر: ورقة arXiv، تم التحديث في 14 أكتوبر 2025
رابط الورقة: https://arxiv.org/abs/2508.09892

الملخص

من المعروف أن طوابير الأولويات الاستعادية الكاملة المثلى تتطلب $O(\log^2 m \log \log m)$ وقتاً لكل عملية، حيث $m$ هو العدد الإجمالي للعمليات المنفذة على هيكل البيانات. وبالمقابل، طوابير الأولويات القياسية (غير الاستعادية) والاستعادية الجزئية تتطلب فقط $O(\log m)$ وقتاً لكل عملية. لا يزال غير واضح ما إذا كانت طوابير الأولويات الاستعادية الكاملة يمكن أن تحقق حد $O(\log m)$ . تدرس هذه الورقة متغيراً مقيداً من طوابير الأولويات الرتيبة، وتثبت أولاً أن البحث عن الحد الأدنى في طوابير الأولويات الاستعادية الرتيبة هو حالة خاصة من مشكلة البحث عن النطاق، ثم تصمم طابور أولويات استعادي رتيب كامل بتعقيد زمني $O(\log m + T(m))$ لكل عملية، وأخيراً تحقق طابور أولويات استعادي رتيب كامل بتعقيد زمني $O(\log m \log \log m)$ لكل عملية.

الخلفية البحثية والدافع

تعريف المشكلة

هياكل البيانات التقليدية تعمل فقط على الحالة "الحالية" ولا يمكنها الاستعلام أو تعديل الحالات السابقة. تم تقديم هياكل البيانات الاستعادية بواسطة Demaine وآخرين، وهي قادرة على تعديل الحالات السابقة ونشر تأثيرات التعديلات إلى الحالة الحالية. وفقاً للوظائف المختلفة، تنقسم إلى:

الاستعادية الجزئية: يمكن تعديل الماضي، لكن يمكن فقط الاستعلام عن الحالة الحالية
الاستعادية الكاملة: يمكن تعديل الماضي والاستعلام عن حالة أي نقطة زمنية

الدافع البحثي

الفجوة في الكفاءة: وجود فجوة كبيرة في التعقيد الزمني بين طوابير الأولويات الاستعادية الكاملة والإصدارات القياسية/الاستعادية الجزئية
التحدي النظري: عدم الوضوح حول ما إذا كانت طوابير الأولويات الاستعادية الكاملة يمكن أن تحقق الحد الأدنى النظري $O(\log m)$
التطبيقات العملية: لطوابير الأولويات الرتيبة قيمة تطبيقية مهمة في سيناريوهات مثل خوارزمية Dijkstra

قيود الطرق الموجودة

التعقيد الزمني لطابور الأولويات الاستعادي الكامل الأمثل هو $O(\log^2 m \log \log m)$
وجود فجوة كبيرة مع التعقيد $O(\log m)$ لطابور الأولويات القياسي
نقص الدراسات المتخصصة للمتغيرات المقيدة (مثل طوابير الأولويات الرتيبة)

المساهمات الأساسية

الاكتشاف النظري: إثبات أن البحث عن الحد الأدنى في طوابير الأولويات الاستعادية الرتيبة يعادل مشكلة البحث عن النطاق
إطار عام: تصميم طابور أولويات استعادي رتيب كامل بتعقيد زمني $O(\log m + T(m))$ ، حيث $T(m)$ هو وقت الاستعلام/التحديث لهيكل البيانات للبحث عن النطاق
تطبيق محدد: تحقيق طابور أولويات استعادي رتيب كامل بتعقيد زمني $O(\log m \log \log m)$ بناءً على أشجار النطاق ثنائية الأبعاد
منظور هندسي: توفير منظور هندسي جديد لفهم طوابير الأولويات الاستعادية

شرح التفاصيل الطريقة

تعريف المهمة

تصميم طابور أولويات استعادي رتيب كامل يدعم العمليات التالية:

Insert(insert(x), t): إدراج العنصر $x$ في الوقت $t$
Delete(insert(x), t): حذف عملية الإدراج في الوقت $t$
Insert(extract-min, t): إدراج عملية استخراج الحد الأدنى في الوقت $t$
Delete(extract-min, t): حذف عملية الاستخراج في الوقت $t$
GetMin(t): إرجاع العنصر الأدنى في الوقت $t$

قيد الرتابة: يجب أن تشكل العناصر المستخرجة تسلسلاً غير متناقص.

الأساس النظري الأساسي

شرط الوجود (Lemma 14)

في طابور الأولويات الرتيب، يوجد العنصر $x$ في الوقت $t$ إذا وفقط إذا:

insertionTime(x) ≤ t
x > lastExtracted(t)

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

البحث الفعال عن آخر عنصر مستخرج (Lemma 16-17)

الرؤية الأساسية: في طابور الأولويات الرتيب، يمكن فقط استخراج العنصر الـ $k$ الأصغر بواسطة عملية الاستخراج الـ $k$ -th em[k].

الخوارزمية:

البحث عن السلف في شجرة أوقات الاستخراج للوقت $t$
تحديد رقم تسلسل تلك العملية $k$
إرجاع العنصر الـ $k$ الأصغر

التعقيد الزمني: $O(\log m)$

التمثيل الهندسي (Lemma 18)

تمثيل طابور الأولويات الرتيب كنقاط على مستوى ثنائي الأبعاد:

يمثل كل عنصر $e$ كنقطة (insertionTime(e), e)
يتحول الاستعلام GetMin(t) إلى البحث عن النقطة ذات أصغر إحداثي $y$ في المستطيل $R(t) = (-\infty, t] \times (\text{lastExtracted}(t), \infty)$

يحول هذا التمثيل مشكلة الاستعلام عن طابور الأولويات بالكامل إلى مشكلة البحث عن النطاق الهندسي.

تصميم هيكل البيانات

ثلاثة هياكل بيانات مساعدة:

$T_{el}$ : شجرة الإحصائيات الترتيبية لتخزين جميع العناصر المدرجة
$T_{em}$ : شجرة الإحصائيات الترتيبية لتخزين جميع أوقات الاستخراج
$T_{ins}$ : هيكل بيانات البحث عن النطاق بأصغر-y لتخزين جميع أزواج (وقت الإدراج، قيمة العنصر)

تطبيق العمليات:

GetMin(t): البحث أولاً عن lastExtracted(t)، ثم الاستعلام عن نطاق المستطيل في $T_{ins}$
Insert/Delete(insert(x), t): تحديث $T_{el}$ و $T_{ins}$
Insert/Delete(extract-min, t): تحديث $T_{em}$

إعداد التجارب

إطار التحليل النظري

تركز الورقة بشكل أساسي على التحليل النظري، وتتحقق من صحة الطريقة بالطرق التالية:

الإثبات الرياضي: إثبات صارم لجميع الـ Lemmas والنظريات الأساسية
تحليل التعقيد: تحليل تفصيلي للتعقيد الزمني والمكاني لكل عملية
التحقق من الصحة: التحقق من صحة الطريقة من خلال الحدس الهندسي والمنطق الخوارزمي

اختيار هيكل البيانات للبحث عن النطاق

اختيار شجرة النطاق ثنائية الأبعاد لـ Mehlhorn و Näher كهيكل بيانات أساسي:

وقت التحديث: $O(\log n \log \log n)$ (مطفأ، يمكن تحويله إلى أسوأ حالة)
وقت الاستعلام: $O(\log n \log \log n)$
التعقيد المكاني: $O(n \log n)$

نتائج التجارب

النتائج النظرية الرئيسية

النظرية 20 (الإطار العام): يوجد طابور أولويات استعادي رتيب كامل بالتعقيدات التالية:

عمليات الاستخراج: $O(\log m)$
عمليات الإدراج: $O(\log m + U(m))$
عمليات الاستعلام: $O(\log m + Q(m))$
التعقيد المكاني: $O(m + S(m))$

حيث $U(m)$ و $Q(m)$ و $S(m)$ هي التحديث والاستعلام والتعقيد المكاني لهيكل البيانات للبحث عن النطاق على التوالي.

النظرية 21 (التطبيق المحدد): التطبيق القائم على شجرة النطاق ثنائية الأبعاد له التعقيدات التالية:

عمليات الاستخراج: $O(\log m)$
عمليات الإدراج: $O(\log m \log \log m)$
عمليات الاستعلام: $O(\log m \log \log m)$
التعقيد المكاني: $O(m \log m)$

مقارنة التعقيد

نوع هيكل البيانات	التعقيد الزمني
طابور الأولويات القياسي	$O(\log m)$
طابور الأولويات الاستعادي الجزئي	$O(\log m)$
طابور الأولويات الاستعادي الكامل (الأمثل المعروف)	$O(\log^2 m \log \log m)$
هذه الورقة: طابور الأولويات الاستعادي الرتيب الكامل	$O(\log m \log \log m)$

حققت هذه الورقة تحسيناً ملحوظاً في التعقيد الزمني لطابور الأولويات الاستعادي الكامل (تحت القيد الرتيب).

الأعمال ذات الصلة

هياكل البيانات الاستعادية

Demaine وآخرون (2007): أول من قدم مفهوم هياكل البيانات الاستعادية، وصمموا طابور أولويات استعادي جزئي
Demaine وآخرون (2015): قدموا طابور أولويات استعادي كامل بتعقيد $O(\log^2 m \log \log m)$
Chen وآخرون (2018): أثبتوا أن بعض هياكل البيانات الاستعادية الكاملة يجب أن تكون أبطأ من الإصدارات الاستعادية الجزئية

طوابير الأولويات الرتيبة

سيناريوهات التطبيق: خوارزمية Dijkstra، جدولة الأحداث، وغيرها
الخصائص: العناصر المستخرجة تشكل تسلسلاً غير متناقص، مما يسهل التحسين مقارنة بطوابير الأولويات العامة

البحث عن النطاق

المشكلة الكلاسيكية: مشكلة أساسية في الهندسة الحسابية
هياكل البيانات: أشجار النطاق، أشجار التقسيم، وغيرها من هياكل البيانات المتخصصة

الخلاصة والمناقشة

الاستنتاجات الرئيسية

المساهمة النظرية: أول من يربط بين مشكلة هياكل البيانات الاستعادية والبحث عن النطاق
تحسين الخوارزمية: تحسين ملحوظ في كفاءة طابور الأولويات الاستعادي الكامل تحت القيد الرتيب
إطار عام: توفير إطار تصميم عام بناءً على هياكل بيانات مختلفة للبحث عن النطاق

القيود

تقييد الاستخدام: ينطبق فقط على طوابير الأولويات الرتيبة، لا يمكن توسيعه مباشرة إلى الحالة العامة
النتائج النظرية: بشكل أساسي تحليل نظري، يفتقر إلى التطبيق العملي والتحقق التجريبي
فجوة التعقيد: لا تزال هناك فجوة عامل $\log \log m$ مع طابور الأولويات القياسي

الاتجاهات المستقبلية

حدد المؤلفون بوضوح ثلاثة اتجاهات بحثية:

دراسة الإصدارات الاستعادية الكاملة لمتغيرات طوابير أولويات مقيدة أخرى
دراسة الحدود العليا لطوابير الأولويات الاستعادية الكاملة العامة
دراسة الحدود الدنيا لطوابير الأولويات الاستعادية

التقييم المتعمق

المميزات

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

أوجه القصور

نطاق التطبيق: محدود بطوابير الأولويات الرتيبة، عمومية محدودة
غياب التجارب: نقص التطبيق العملي واختبارات الأداء
تحليل الحد الأدنى: لم يتم توفير تحليل الحد الأدنى المقابل
عوامل ثابتة: لم يتم النظر في تأثير العوامل الثابتة في التحليل النظري

التأثير

المساهمة النظرية: توفير منظور هندسي جديد لبحث هياكل البيانات الاستعادية
قيمة المنهجية: إظهار كيفية الاستفادة من الهيكل الخاص للمشكلة للتحسين
الأهمية الإرشادية: قد تلهم البحث عن إصدارات استعادية لهياكل بيانات مقيدة أخرى

السيناريوهات القابلة للتطبيق

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

المراجع

تستشهد الورقة بـ 13 مرجعاً ذا صلة، تشمل بشكل أساسي:

Demaine وآخرون (2007) - العمل الرائد في هياكل البيانات الاستعادية
Demaine وآخرون (2015) - طابور الأولويات الاستعادي الكامل الأمثل الحالي
Mehlhorn و Näher (1990) - العمل الكلاسيكي في أشجار النطاق ثنائية الأبعاد
Agarwal (2018) - مسح مشاكل البحث عن النطاق

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