الكومات وأرتال الأولوية - دليل دراسة شامل

📑 جدول المحتويات

1. مقدمة عن المجموعات
2. نوع البيانات المجردة لرتل الأولوية
3. تطبيقات رتل الأولوية
4. الأشجار الثنائية الكاملة
5. تعريف الكومة وخصائصها
6. عمليات الكومة
7. التنفيذ بلغة جافا
8. تحليل التعقيد الزمني
9. ترتيب الكومة
10. مسائل تدريبية

1. مقدمة عن المجموعات

فريد بروكس: "أرني كودك وأخفي هياكل بياناتك، وسأبقى في حيرة. أرني هياكل بياناتك، وعادةً لن أحتاج كودك؛ سيكون الأمر واضحًا."

المجموعة هي نوع بيانات يخزن مجموعات من العناصر. للمجموعات المختلفة عمليات أساسية مختلفة وتُنفذ بهياكل بيانات مختلفة.

المجموعات الشائعة

نوع البيانات	العمليات الأساسية	هيكل البيانات
المكدس	PUSH, POP	قائمة مرتبطة، مصفوفة متغيرة الحجم
الرتل	ENQUEUE, DEQUEUE	قائمة مرتبطة، مصفوفة متغيرة الحجم
رتل الأولوية	INSERT, DELETE-MAX	كومة ثنائية
جدول الرموز	PUT, GET, DELETE	شجرة بحث ثنائية، جدول تجزئة
المجموعة	ADD, CONTAINS, DELETE	شجرة بحث ثنائية، جدول تجزئة

2. نوع البيانات المجردة لرتل الأولوية

التعريف

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

الاختلافات الرئيسية عن المجموعات الأخرى

المكدس: إزالة العنصر المُضاف مؤخرًا (آخر داخل أول خارج)
الرتل: إزالة العنصر المُضاف أولاً (أول داخل أول خارج)
رتل عشوائي: إزالة عنصر عشوائي
رتل الأولوية: إزالة العنصر الأكبر (أو الأصغر)

واجهة برمجة رتل الأولوية (جافا)

public class MaxPQ<Key extends Comparable<Key>>
{
    // إنشاء رتل أولوية فارغ
    MaxPQ()
    
    // إنشاء رتل أولوية بمفاتيح معطاة
    MaxPQ(Key[] a)
    
    // إدراج مفتاح في رتل الأولوية
    void insert(Key v)
    
    // إرجاع وإزالة المفتاح الأكبر
    Key delMax()
    
    // هل رتل الأولوية فارغ؟
    boolean isEmpty()
    
    // إرجاع المفتاح الأكبر (بدون إزالته)
    Key max()
    
    // عدد العناصر في رتل الأولوية
    int size()
}
                

⚠️ مهم: النوع العام Key يجب أن ينفذ الواجهة Comparable<Key> حتى يمكن ترتيب العناصر.

مثال على العمليات

مثال: عمليات رتل الأولوية

العملية	المعامل	القيمة المُرجعة	المحتوى (غير مرتب)
إدراج	P	-	P
إدراج	Q	-	P Q
إدراج	E	-	P Q E
إزالة الأكبر	-	Q	P E
إدراج	X	-	P E X
إدراج	A	-	P E X A
إدراج	M	-	P E X A M
إزالة الأكبر	-	X	P E M A

3. تطبيقات رتل الأولوية

رتلات الأولوية تعمم المكدسات والرتلات والرتلات العشوائية، ولها تطبيقات عديدة في العالم الواقعي:

🌟 تطبيقات من العالم الواقعي

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

4. الأشجار الثنائية الكاملة

الشجرة الثنائية

الشجرة الثنائية إما أن تكون فارغة أو عقدة بها روابط إلى أشجار ثنائية يسرى ويمنى (كل عقدة لها طفلان على الأكثر).

الشجرة الثنائية الكاملة

الشجرة الكاملة تكون متوازنة تمامًا، باستثناء المستوى السفلي (ربما). جميع المستويات ممتلئة تمامًا باستثناء المستوى الأخير، الذي يُملأ من اليسار إلى اليمين.

مثال على شجرة ثنائية كاملة (N = 16، الارتفاع = 4)

                    ○
                   / \
                  ○   ○
                 / \ / \
                ○ ○ ○ ○
               /\\/\\/\\/\
              ○○○○○○○○○

📐 خاصية مهمة

ارتفاع شجرة كاملة تحتوي على N عقدة هو ⌊lg N⌋

الارتفاع يزداد فقط عندما تكون N قوة للعدد 2.

هذا الارتفاع اللوغاريتمي هو ما يجعل الكومات فعالة!

لماذا الأشجار الثنائية الكاملة؟

✅ المزايا

ارتفاع لوغاريتمي مضمون
يمكن تخزينها بكفاءة في مصفوفة
لا حاجة لروابط صريحة
الانتقال بين العناصر سهل باستخدام فهارس المصفوفة

⚠️ القيود

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

5. تعريف الكومة وخصائصها

الكومة الثنائية

الكومة الثنائية هي تمثيل بمصفوفة لشجرة ثنائية كاملة مرتبة على شكل كومة.

خاصيتان أساسيتان

1. خاصية ترتيب الكومة

لكل عقدة داخلية v غير الجذر:

key(v) ≥ key(parent(v))

هذا يعني: مفتاح الوالد ليس أصغر من مفاتيح الأبناء

أو بصيغة أخرى: مفتاح كل عقدة يجب أن يكون أصغر من أو مساويًا لمفتاح والدها.

2. خاصية الشجرة الثنائية الكاملة

يجب أن تكون الشجرة شجرة ثنائية كاملة (كما تم تعريفها أعلاه).

أنواع الكومات

نوع الكومة	الخاصية	ما يحتويه الجذر
كومة قصوى (Max Heap)	الوالد ≥ الأبناء	العنصر الأكبر
كومة صغرى (Min Heap)	الوالد ≤ الأبناء	العنصر الأصغر

📝 ملاحظة: بشكل افتراضي، عندما نقول "كومة" فإننا نقصد عادةً كومة قصوى. يركز دليل الدراسة هذا على الكومات القصوى، لكن المفاهيم تنطبق بشكل متساوٍ على الكومات الصغرى مع عكس المقارنات.

التمثيل بالمصفوفة

فهارس المصفوفة للانتقال

في كومة مخزنة في المصفوفة a[] بدءًا من الفهرس 1:

الجذر: a[1]
والد العقدة في الموضع k: a[k/2]
الابن الأيسر للعقدة في الموضع k: a[2k]
الابن الأيمن للعقدة في الموضع k: a[2k+1]

تصور الكومة (كومة قصوى)

التمثيل كشجرة:

           T (1)
          / \
        S(2) R(3)
       / \   / \
     P(4)N(5)O(6)A(7)
     /\  /\
   E I  H G
   8 9 10 11

التمثيل كمصفوفة:

ملاحظة: الفهرس 0 غير مستخدم (نبدأ من الفهرس 1)

🎯 خصائص أساسية

المفتاح الأكبر يكون دائمًا في a[1] (الجذر)
يمكننا التنقل في الشجرة باستخدام عمليات حسابية بسيطة على فهارس المصفوفة
لا حاجة لروابط صريحة (مؤشرات)!
كفاءة في المساحة: نحتاج فقط مصفوفة بحجم N+1

6. عمليات الكومة

6.1 عملية الإدراج (الطفو لأعلى)

خوارزمية الإدراج

إضافة المفتاح الجديد في نهاية المصفوفة (الموضع N+1)
تصبح العقدة الجديدة "العقدة الأخيرة" الجديدة للشجرة الكاملة
الطفو لأعلى: المقارنة مع الوالد والتبادل إذا لزم الأمر
التكرار حتى استعادة ترتيب الكومة

دالة المساعدة للطفو

private void swim(int k) {
    // طالما لسنا في الجذر AND الطفل > الوالد
    while (k > 1 && less(k/2, k)) {
        exch(k, k/2);  // التبادل مع الوالد
        k = k/2;        // الانتقال لأعلى إلى الوالد
    }
}
                

دالة الإدراج

public void insert(Key x) {
    pq[++N] = x;  // الإضافة في النهاية وزيادة الحجم
    swim(N);      // استعادة ترتيب الكومة
}
                

مثال: إدراج 'S' في الكومة

قبل:                بعد الإضافة:         بعد الطفو:
     T                    T                    S
    / \                  / \                  / \
   P   R                P   R                T   R
  / \                  / \ /                / \ /
 N   H                N  H S              N  H P
    
الكومة: T P R N H    → T P R N H S  →  S T R N H P
                     (تَنْقُض)         (تم الاستعادة)

⏱️ التعقيد الزمني للإدراج

على الأكثر 1 + lg N مقارنة

لماذا؟ في أسوأ حالة، نطفو من الأسفل إلى أعلى الشجرة، والارتفاع هو ⌊lg N⌋.

6.2 عملية حذف الأكبر (الغوص لأسفل)

خوارزمية حذف الأكبر

حفظ قيمة الجذر (الأكبر) لإرجاعها لاحقًا
تبادل الجذر مع العقدة الأخيرة (في الموضع N)
إنقاص N (إزالة الموضع الأخير)
الغوص لأسفل: المقارنة مع الأبناء والتبادل مع الابن الأكبر إذا لزم الأمر
التكرار حتى استعادة ترتيب الكومة
إرجاع قيمة الأكبر المحفوظة

دالة المساعدة للغوص

private void sink(int k) {
    while (2*k <= N) {  // طالما هناك طفل واحد على الأقل
        int j = 2*k;    // الابن الأيسر
        
        // اختيار الابن الأكبر
        if (j < N && less(j, j+1)) j++;
        
        // إذا كان الوالد >= الابن الأكبر، تم الانتهاء
        if (!less(k, j)) break;
        
        exch(k, j);  // التبادل مع الابن الأكبر
        k = j;        // الانتقال لأسفل
    }
}
                

دالة حذف الأكبر

public Key delMax() {
    Key max = pq[1];      // الحصول على الجذر (الأكبر)
    exch(1, N--);         // التبادل مع الأخير، إنقاص N
    sink(1);              // استعادة ترتيب الكومة
    pq[N+1] = null;       // منع بقاء مراجع غير ضرورية
    return max;
}
                

مثال: حذف الأكبر من الكومة

قبل:                بعد التبادل:         بعد الغوص:
     T                    H                    S
    / \                  / \                  / \
   S   R                S   R                P   R
  / \ / \              / \ /                / \ /
 P  N O  A            P  N O  A            N  H O  A

إزالة T  →  التبادل مع H  →  غوص H لأسفل
(إرجاع T)   (تَنْقُض الترتيب)   (تم الاستعادة)

❓ لماذا نتبادل مع الابن الأكبر؟

إذا تبادلنا مع الابن الأصغر، قد ينتهي بنا المطاف بوالد أصغر من ابنه الآخر، مما ينقض ترتيب الكومة. بالمبادلة مع الابن الأكبر، نضمن أن كلا الابنين سيكونان أصغر من الوالد الذي تمت ترقيته.

⏱️ التعقيد الزمني لحذف الأكبر

على الأكثر 2 lg N مقارنة

لماذا 2؟ في كل مستوى، نقارن بين الابنين (مقارنة واحدة) ثم نقارن مع الوالد (مقارنة أخرى). الارتفاع هو ⌊lg N⌋.

💡 "مبدأ بيتر": في الطفو، يتم ترقية العقدة إلى مستوى عجزها (لا يمكنها الصعود أكثر). في الغوص، هناك "صراع على السلطة" حيث يتم ترقية المرؤوس الأفضل!

7. التنفيذ الكامل بلغة جافا

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;         // مصفوفة لتخزين الكومة
    private int N;            // عدد العناصر
    
    // المُنشئ
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity + 1];
    }
    
    // هل رتل الأولوية فارغ؟
    public boolean isEmpty() {
        return N == 0;
    }
    
    // عدد العناصر
    public int size() {
        return N;
    }
    
    // إدراج مفتاح
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
    
    // حذف وإرجاع الأكبر
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;  // منع بقاء مراجع غير ضرورية
        return max;
    }
    
    /*******************************************
     * دوال مساعدة لعمليات الكومة
     *******************************************/
    
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
    
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
    
    /*******************************************
     * دوال مساعدة للمقارنات والتباديل
     *******************************************/
    
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}
                

📝 ملاحظات عن التنفيذ:

فهارس المصفوفة تبدأ من 1 (الفهرس 0 غير مستخدم)
للبساطة، هذا التنفيذ يستخدم سعة ثابتة (يمكن جعله متغير الحجم)
النوع العام Key يجب أن ينفذ الواجهة Comparable
تعيين pq[N+1] = null يمنع بقاء مراجع غير ضرورية (يسمح بجمع القمامة)

8. تحليل التعقيد الزمني

التنفيذات الأولية مقابل الكومة الثنائية

التنفيذ	الإدراج	حذف الأكبر	الحصول على الأكبر
مصفوفة غير مرتبة	1	N	N
مصفوفة مرتبة	N	1	1
الكومة الثنائية	log N	log N	1

🎯 لماذا الكومة الثنائية هي الأمثل

عمليات لوغاريتمية: كل من الإدراج وحذف الأكبر هما O(log N)
وقت ثابت للأكبر: الحصول على العنصر الأكبر هو O(1)
كفاءة في المساحة: نحتاج فقط O(N) مساحة
تنفيذ بسيط: مجرد مصفوفة بدالتين مساعدتين

تحليل مفصل

عملية الإدراج

أفضل حالة: O(1) - العنصر موجود بالفعل في موضعه الصحيح
أسوأ حالة: O(log N) - الطفو من الأسفل إلى الأعلى
متوسط الحالة: O(log N)

عملية حذف الأكبر

أفضل حالة: O(log N) - لا يزال بحاجة للتحقق من الأبناء
أسوأ حالة: O(log N) - الغوص من الأعلى إلى الأسفل
متوسط الحالة: O(log N)

💡 لماذا log N؟ لأن ارتفاع الشجرة الثنائية الكاملة ذات N عقدة هو ⌊log₂ N⌋، وفي أسوأ حالة، ننتقل من أحد الطرفين إلى الآخر.

9. ترتيب الكومة

خوارزمية ترتيب الكومة

ترتيب الكومة هي خوارزمية ترتيب تعتمد على المقارنة تستخدم كومة ثنائية لترتيب مصفوفة في زمن O(N log N) باستخدام مساحة إضافية O(1).

نظرة عامة على الخوارزمية

بناء الكومة: إعادة ترتيب المصفوفة لتصبح كومة
الترتيب النزولي: إزالة الأكبر (الجذر) بشكل متكرر ووضعه في النهاية

استخدام رتل الأولوية للترتيب

// طريقة بسيطة باستخدام رتل الأولوية
public static void sort(Comparable[] a) {
    int N = a.length;
    MaxPQ pq = new MaxPQ(N);
    
    // المرحلة 1: إدراج جميع العناصر
    for (int i = 0; i < N; i++)
        pq.insert(a[i]);
    
    // المرحلة 2: الإزالة بالترتيب
    for (int i = N-1; i >= 0; i--)
        a[i] = pq.delMax();
}
                

التعقيد الزمني

⏱️ تحليل وقت التشغيل

بناء الكومة: O(N log N) مع إدراجات متكررة
إزالة جميع العناصر: O(N log N)
المجموع: O(N log N)
المساحة: O(N) للكومة

المقارنة مع خوارزميات ترتيب أخرى

الخوارزمية	التعقيد الزمني	المساحة	مستقر؟
ترتيب الإدراج	O(N²)	O(1)	✅ نعم
ترتيب الاختيار	O(N²)	O(1)	❌ لا
ترتيب الدمج	O(N log N)	O(N)	✅ نعم
ترتيب الكومة	O(N log N)	O(N)	❌ لا
ترتيب سريع	O(N log N)*	O(log N)	❌ لا

* متوسط الحالة؛ أسوأ حالة هي O(N²)

✅ مزايا ترتيب الكومة

أداء مضمون O(N log N)
ترتيب في نفس المكان (لا حاجة لمصفوفة إضافية)
لا يوجد سلوك تربيعي في أسوأ حالة
تنفيذ بسيط

⚠️ عيوب ترتيب الكومة

غير مستقر
أداء ضعيف في ذاكرة التخزين المؤقت
أبطأ من الترتيب السريع عمليًا
غير تكيُّفي (لا يستفيد من الترتيب الجزئي)

10. المسائل التدريبية والمفاهيم الأساسية

مسألة تدريبية 1: بناء كومة قصوى

المسألة

أدرج العناصر التالية في كومة قصوى فارغة بالترتيب: 2, 5, 16, 4, 10, 23, 39, 18, 26, 15

خطوات الحل

يتطلب الحل بناء الكومة عنصرًا تلو الآخر، والطفو لأعلى بعد كل إدراج. الكومة النهائية ينبغي أن تكون:

           39
          /  \
        26    23
       / \   / \
     18  15 16  5
     / \ /
    2  4 10

المصفوفة: [-, 39, 26, 23, 18, 15, 16, 5, 2, 4, 10]

مسألة تدريبية 2: عمليات الحذف

المسألة

من الكومة أعلاه، نفّذ ثلاث عمليات deleteMax(). اعرض الكومة بعد كل عملية حذف.

تلميح

تذكر: تبادل الجذر مع العنصر الأخير، إزالة الأخير، ثم الغوص لأسفل.

مسألة تدريبية 3: هل هذه كومة؟

المسألة

حدّد ما إذا كانت الشجرة الثنائية التالية كومة قصوى صالحة:

        8
       / \
      30  12
     / \  / \
    60 40 50 60

الإجابة

لا - أصغر عنصر في الكومة يجب أن يكون دائمًا في عقدة الجذر. هنا، 8 هي الجذر لكنها أصغر من أبنائها (30 و12)، مما ينقض خاصية ترتيب الكومة.

🎯 مفاهيم أساسية للتذكر

شجرة ثنائية كاملة: جميع المستويات ممتلئة باستثناء الأخير (ربما)، والذي يُمتلأ من اليسار لليمين
خاصية ترتيب الكومة: الوالد ≥ الأبناء (كومة قصوى) أو الوالد ≤ الأبناء (كومة صغرى)
التمثيل بالمصفوفة: الوالد في k/2، الأبناء في 2k و2k+1
الجذر في الفهرس 1: يجعل الرياضيات أبسط (الوالد = k/2)
الأكبر دائمًا في الجذر: وصول O(1) للعنصر الأكبر
الارتفاع هو ⌊log N⌋: يضمن عمليات لوغاريتمية
الطفو لأعلى: يُستخدم بعد الإدراج، يقارن مع الوالد
الغوص لأسفل: يُستخدم بعد حذف الأكبر، يقارن مع الابن الأكبر
كلا العمليتين: تعقيد زمني O(log N)
لا حاجة لروابط صريحة: العمليات الحسابية على المصفوفة تتعامل مع التنقل

📚 نصائح للدراسة

ارسمها: تصوّر عمليات الكومة برسم الأشجار
تَتبّع الكود: اتّبع عمليات الطفو والغوص خطوة بخطوة
افهم السبب: اعرف لماذا نتبادل مع الابن الأكبر في الغوص
تمرّن على فهرسة المصفوفة: اعتد على k/2، 2k، 2k+1
احفظ التعقيدات: الإدراج O(log N)، حذف الأكبر O(log N)، الحصول على الأكبر O(1)
قارن بين التنفيذات: افهم المقايضات مقابل هياكل البيانات الأخرى

أخطاء شائعة يجب تجنبها

❌ بدء المصفوفة من الفهرس 0 (يجعل رياضيات الوالد/الابن أصعب)
❌ نسيان تعيين العناصر المحذوفة إلى null (تسرّب ذاكرة)
❌ التبادل مع الابن الأصغر في الغوص (ينقض ترتيب الكومة)
❌ عدم التحقق من حدود المصفوفة في الغوص
❌ الخلط بين خصائص الكومة القصوى والكومة الصغرى
❌ الاعتقاد بأن الكومة مرتبة (هي مرتبة جزئيًا فقط)