التحويل والحل: الكومة واختزال المشكلات
تغطي هذه الوحدة استراتيجية التحويل والحل في تصميم الخوارزميات، مع التركيز على بنية بيانات الكومة (Heap)، خوارزمية الترتيب بالكومة (Heapsort)، ومفهوم اختزال المشكلات (Problem Reduction).
Transform-and-Conquer: Heaps and Problem Reduction
This module covers the Transform-and-Conquer algorithm design strategy, focusing on the Heap data structure, Heapsort algorithm, and the concept of Problem Reduction.
أهداف التعلم
- تطبيق خوارزمية الترتيب بالكومة (Heapsort) في نطاق المشكلات.
- التعرف على مفهوم اختزال المشكلات (Problem Reduction) واستخدامه.
- فهم خصائص الكومة وتمثيلها باستخدام المصفوفات.
- تحليل كفاءة خوارزمية الترتيب بالكومة في أسوأ الحالات والمتوسطة.
- Apply the heapsorting in problem domain.
- Recognize problem reduction.
- Understand heap properties and their array representation.
- Analyze the worst-case and average-case efficiency of Heapsort.
1 تعريف الكومة وخصائصها
1 Heap Definition and Properties
الكومة هي شجرة ثنائية شبه مكتملة يكون فيها مفتاح كل أب أكبر من أو يساوي مفاتيح أبنائه، مثل هرم إداري يكون فيه المدير دائماً أعلى رتبة من مرؤوسيه.
A heap is an essentially complete binary tree where each parent's key is greater than or equal to its children's keys, like a corporate hierarchy where a manager always outranks subordinates.
الكومة (Heap) هي شجرة ثنائية تحتوي على مفاتيح في عقدها (مفتاح واحد لكل عقدة) وتحقق شرطين أساسيين:
- هي شجرة شبه مكتملة (Essentially complete)، أي أن جميع مستوياتها ممتلئة باستثناء المستوى الأخير الذي قد تنقصه بعض العقد من جهة اليمين.
- شرط سيادة الأب: المفتاح في كل عقدة يجب أن يكون أكبر من أو يساوي جميع المفاتيح في أبنائها (وأحفادها).
من الخصائص المهمة للكومة أن الجذر يحتوي دائماً على المفتاح الأكبر، وأن كل شجرة فرعية داخل الكومة تعتبر كومة بحد ذاتها.
ارتفاع الكومة التي تحتوي على n من العقد هو h = ⌊log2 n⌋.
A heap is a binary tree with keys at its nodes (one key per node) that satisfies two main conditions:
- It is essentially complete, meaning all its levels are full except possibly the last level, where only some rightmost keys may be missing.
- Parental dominance: The key at each node is ≥ all keys in its children (and descendants).
Important properties include: the root always contains the largest key, and every subtree rooted at every node of a heap is also a heap.
The height of a heap with n nodes is h = ⌊log2 n⌋.
عناصر الكومة مرتبة من الأعلى إلى الأسفل (على طول أي مسار ينزل من الجذر)، ولكنها غير مرتبة من اليسار إلى اليمين.
هذا الترتيب الجزئي هو ما يجعل الكومة فعالة جداً في استخراج العنصر الأكبر (أو الأصغر في حالة Min-Heap) دون الحاجة لترتيب كامل العناصر، مما يجعلها البنية المثالية لتنفيذ طوابير الأولوية (Priority Queues).
Heap's elements are ordered top-down (along any path down from its root), but they are not ordered left to right.
This partial ordering is what makes the heap highly efficient for extracting the maximum (or minimum in a Min-Heap) element without maintaining a fully sorted structure, making it the ideal underlying data structure for Priority Queues.
لماذا لا يُشترط ترتيب عناصر الكومة من اليسار إلى اليمين؟ Why is there no requirement for heap elements to be ordered from left to right?
لأن الهدف الأساسي للكومة هو الوصول السريع للعنصر الأكبر (الجذر) والحفاظ على شجرة متوازنة لتحديثها بسرعة، والترتيب الصارم من اليسار لليمين سيتطلب جهداً إضافياً (O(n)) عند كل إدراج، مما يلغي كفاءة الكومة (O(log n)).
Because the primary goal of a heap is fast access to the maximum element (the root) and maintaining a balanced tree for quick updates. Strict left-to-right ordering would require O(n) effort for insertions/deletions, destroying the O(log n) efficiency.
2 تمثيل الكومة باستخدام المصفوفة
2 Heap's Array Representation
يمكن تخزين الكومة في مصفوفة عادية حيث يتم حساب مواقع الأبناء والآباء باستخدام عمليات حسابية بسيطة على الأدلة (Indices).
A heap can be stored in a standard array where the positions of children and parents are calculated using simple index arithmetic.
نظراً لأن الكومة شجرة شبه مكتملة، يمكن تمثيلها بسهولة وكفاءة كمصفوفة. يتم تخزين العناصر بترتيب من أعلى لأسفل ومن اليسار لليمين.
إذا افترضنا أن الفهرسة تبدأ من 1 (لتسهيل الحسابات)، فإن:
- الابن الأيسر للعقدة j يقع في الدليل 2j.
- الابن الأيمن للعقدة j يقع في الدليل 2j+1.
- الأب للعقدة j يقع في الدليل ⌊j/2⌋.
- العقد الداخلية (الآباء) تشغل المواقع الأولى حتى ⌊n/2⌋ في المصفوفة.
Because a heap is an essentially complete binary tree, it can easily and efficiently be represented as an array. Elements are stored in top-down left-to-right order.
Assuming 1-based indexing (for convenience):
- The left child of node j is at 2j.
- The right child of node j is at 2j+1.
- The parent of node j is at ⌊j/2⌋.
- Parental (interior) nodes are located in the first ⌊n/2⌋ locations of the array.
هذا التمثيل يلغي الحاجة لاستخدام المؤشرات (Pointers) لربط العقد، مما يوفر مساحة الذاكرة ويحسن من أداء الذاكرة المخبئية (Cache locality).
العمليات الحسابية (الضرب والقسمة على 2) يمكن تنفيذها بسرعة فائقة في المعالجات باستخدام إزاحة البتات (Bitwise shifts).
This representation eliminates the need for pointers to link nodes, saving memory space and vastly improving cache locality.
The arithmetic operations (multiplying and dividing by 2) can be executed extremely fast at the hardware level using bitwise shifts.
ماذا يحدث لمعادلات الأدلة إذا بدأنا فهرسة المصفوفة من 0 بدلاً من 1؟ What happens to the index formulas if we start array indexing from 0 instead of 1?
ستتغير المعادلات لتصبح: الابن الأيسر = 2j + 1، الابن الأيمن = 2j + 2، والأب = ⌊(j-1)/2⌋.
The formulas change to: Left child = 2j + 1, Right child = 2j + 2, and Parent = ⌊(j-1)/2⌋.
3 بناء الكومة (من الأسفل للأعلى)
3 Heap Construction (Bottom-up)
يتم بناء الكومة بالبدء من آخر عقدة أب والعمل صعوداً نحو الجذر، مع إصلاح كل شجرة فرعية لتصبح كومة صحيحة.
Heap construction works by starting from the last parental node and moving up to the root, fixing each subtree to be a valid heap along the way.
خوارزمية بناء الكومة من الأسفل للأعلى (Bottom-up):
- الخطوة 0: تهيئة المصفوفة بالمفاتيح المعطاة.
- الخطوة 1 (Heapify): البدء من آخر عقدة داخلية (أب) في الموقع ⌊n/2⌋، والتحقق من شرط الكومة للشجرة التي جذرها هذه العقدة. إذا لم يتحقق الشرط، يتم تبديل العقدة مع أكبر أبنائها، وتستمر عملية التبديل نزولاً حتى يتحقق الشرط.
- الخطوة 2: تكرار الخطوة 1 للعقدة الداخلية السابقة، والاستمرار صعوداً حتى نصل إلى الجذر (الموقع 1).
Bottom-up Heap Construction algorithm:
- Step 0: Initialize the array with the given keys.
- Step 1 (Heapify): Starting with the last (rightmost) parental (interior) node at index ⌊n/2⌋, fix the heap rooted at it. If it doesn't satisfy the heap condition, keep exchanging it with its largest child until the heap condition holds.
- Step 2: Repeat Step 1 for the preceding parental node, moving bottom-up to the root (index 1), pushing elements down as needed.
هذه الطريقة فعالة جداً وتستغرق وقتاً خطياً O(n) في أسوأ الحالات، وهو أفضل من بناء الكومة عن طريق الإدراج المتتالي (Top-down) الذي يستغرق O(n log n).
السبب هو أن معظم العقد تقع في أسفل الشجرة وتتطلب عدداً قليلاً جداً من المقارنات للنزول.
This method is highly efficient, taking O(n) time in the worst case, which is strictly better than building a heap via successive insertions (Top-down) which takes O(n log n).
The mathematical reason is that most nodes are at the bottom of the tree and require very few comparisons to sift down.
ALGORITHM HeapBottomUp(H[1..n])
for i <- ⌊n/2⌋ downto 1 do
k <- i; v <- H[k]
heap <- false
while not heap and 2*k <= n do
j <- 2*k
if j < n // there are two children
if H[j] < H[j+1] j <- j+1
if v >= H[j]
heap <- true
else H[k] <- H[j]; k <- j
H[k] <- vلماذا نبدأ عملية البناء من العقدة ⌊n/2⌋ وليس من العقدة n؟ Why do we start the construction process from node ⌊n/2⌋ and not from node n?
لأن العقد من ⌊n/2⌋ + 1 إلى n هي أوراق (Leaves)، والورقة بمفردها تعتبر كومة صحيحة ولا تحتاج إلى إصلاح.
Because nodes from ⌊n/2⌋ + 1 to n are leaves. A single leaf node trivially satisfies the heap condition and doesn't need to be heapified.
4 إدراج عنصر جديد في الكومة
4 Insert a New Element into a Heap
لإضافة عنصر، نضعه في نهاية الكومة ثم نجعله يطفو للأعلى بتبديله مع أبيه حتى يستقر في مكانه الصحيح.
To add an element, place it at the end of the heap and let it bubble up by swapping with its parent until it reaches its correct position.
عملية الإدراج (Top Down order):
- يتم إدراج العنصر الجديد في الموضع الأخير في الكومة (زيادة حجم المصفوفة بمقدار 1).
- تتم مقارنة العنصر الجديد مع أبيه. إذا كان يخالف شرط الكومة (أي أكبر من أبيه في حالة Max-Heap)، يتم التبديل بينهما.
- تستمر هذه المقارنة والتبديل صعوداً في الشجرة حتى يتحقق شرط الكومة أو يصل العنصر إلى الجذر.
كفاءة هذه العملية هي O(log n) لأن العنصر قد يصعد مساراً بطول ارتفاع الشجرة.
Insertion process (Top Down order):
- Insert the new element at the last position in the heap (size++).
- Compare the new element with its parent and, if it violates the heap condition (e.g., larger than parent in a Max-Heap), exchange them.
- Continue comparing the new element with nodes up the tree until the heap condition is satisfied or it reaches the root.
The efficiency is O(log n) because the element may travel up the height of the tree.
هذه العملية هي الأساس لبناء الكومة من الأعلى للأسفل (Top-Down Construction)، حيث نبدأ بمصفوفة فارغة وندرج العناصر واحداً تلو الآخر.
ورغم بساطتها، إلا أن بناء كومة كاملة بهذه الطريقة يستغرق O(n log n)، وهو أبطأ من طريقة Bottom-Up.
This operation is the basis for Top-Down Heap Construction, where we start with an empty array and insert elements one by one.
While intuitive, building an entire heap this way takes O(n log n) time, making it asymptotically slower than the O(n) Bottom-Up approach.
في أسوأ الحالات، كم عدد التبديلات المطلوبة لإدراج عنصر في كومة تحتوي على 1023 عنصراً؟ In the worst case, how many swaps are required to insert an element into a heap with 1023 elements?
ارتفاع الكومة هو ⌊log2(1023)⌋ = 9. في أسوأ الحالات (إذا كان العنصر الجديد هو الأكبر)، سيصعد من الورقة إلى الجذر، مما يتطلب 9 تبديلات.
The height of the heap is ⌊log2(1023)⌋ = 9. In the worst case (if the new element is the largest), it will bubble up from the leaf to the root, requiring 9 swaps.
5 خوارزمية الترتيب بالكومة (Heapsort)
5 Heapsort Algorithm
الترتيب بالكومة يحول المصفوفة إلى كومة، ثم يسحب العنصر الأكبر (الجذر) مراراً وتكراراً ويضعه في نهاية المصفوفة.
Heapsort turns the array into a heap, then repeatedly extracts the largest element (the root) and places it at the end of the array.
تتكون خوارزمية الترتيب بالكومة من مرحلتين:
- المرحلة 1: بناء كومة (Max-Heap) لقائمة معطاة من n مفتاح (باستخدام طريقة Bottom-up).
- المرحلة 2: تكرار عملية إزالة الجذر n-1 مرة. في كل مرة، يتم تبديل المفتاح في الجذر (الأكبر) مع المفتاح في آخر ورقة (أقصى اليمين). ثم يتم تقليل حجم الكومة بمقدار 1، ويتم تطبيق عملية الإصلاح (Heapify) على الجذر الجديد لدفعه للأسفل حتى يتحقق شرط الكومة مجدداً.
The Heapsort algorithm consists of two stages:
- Stage 1: Construct a heap (Max-Heap) for a given list of n keys (typically using the Bottom-up method).
- Stage 2: Repeat the operation of root removal n-1 times. In each iteration, exchange the key in the root (the maximum) with the last (rightmost) leaf. Decrease the heap size by 1, and repeatedly swap the new root with its larger child until the heap condition holds again (Heapify).
كفاءة الخوارزمية في أسوأ الحالات والمتوسطة هي Θ(n log n). المرحلة الأولى تستغرق O(n) والمرحلة الثانية تستغرق O(n log n).
الخوارزمية تعمل في نفس المكان (In-place) مما يجعلها ممتازة من حيث استهلاك الذاكرة، لكنها غير مستقرة (Not stable) لأن التبديل مع الورقة الأخيرة قد يغير الترتيب النسبي للعناصر المتساوية.
Both worst-case and average-case efficiency are Θ(n log n). Stage 1 takes O(n) and Stage 2 takes O(n log n).
The algorithm is in-place (requires O(1) extra space), making it highly memory efficient compared to Mergesort. However, it is not stable; the long-distance swap of the root with the last leaf can disrupt the relative order of equal elements.
لماذا نستخدم Max-Heap لترتيب المصفوفة تصاعدياً بدلاً من Min-Heap؟ Why do we use a Max-Heap to sort an array in ascending order instead of a Min-Heap?
لأن Max-Heap يضع العنصر الأكبر في الجذر. عند إزالته، نضعه في نهاية المصفوفة (مكانه الصحيح في الترتيب التصاعدي) ونقلل حجم الكومة، مما يسمح لنا بالترتيب في نفس المصفوفة (In-place) دون الحاجة لمصفوفة إضافية.
Because a Max-Heap places the largest element at the root. When extracted, we swap it to the end of the array (its correct sorted position) and shrink the heap boundary, allowing us to sort entirely in-place without extra memory.
6 اختزال المشكلات (Problem Reduction)
6 Problem Reduction
اختزال المشكلة يعني تحويل مشكلة لا نعرف حلها إلى مشكلة أخرى نمتلك خوارزمية جاهزة لحلها.
Problem reduction means transforming a problem you don't know how to solve into a different problem for which an algorithm is already available.
اختزال المشكلات هو تنويع على استراتيجية التحويل والحل (Transform-and-Conquer).
الفكرة هي: لحل المشكلة P، نقوم بتحويلها إلى المشكلة Q، ثم نستخدم خوارزمية حل Q كجزء من حل P. الرمز P ≤ Q يعني أن المشكلة P تُختزل إلى المشكلة Q.
لكي يكون هذا الاختزال ذا قيمة عملية، يجب أن يكون الوقت المشترك لعملية التحويل وحل المشكلة الجديدة أقل من وقت حل المشكلة الأصلية باستخدام طرق أخرى (مثل القوة الغاشمة).
Problem Reduction is a variation of transform-and-conquer.
To solve problem P, transform it into a different problem Q for which an algorithm is already available. Notation: P ≤ Q means P reduces to Q. To solve P, first solve Q then use the solution to Q in the solution to P.
To be of practical value, the combined time of the transformation and solving the other problem should be smaller than solving the problem as given by another method (e.g., brute force).
من الأمثلة الشهيرة: حساب المضاعف المشترك الأصغر (LCM) باختزاله إلى القاسم المشترك الأكبر (GCD) باستخدام المعادلة LCM(x, y) = (x * y) / GCD(x, y).
أمثلة أخرى تشمل تحويل مشكلات إيجاد القيمة العظمى إلى إيجاد القيمة الصغرى، أو اختزال مشكلات الألغاز إلى مشكلات البحث في الرسوم البيانية (Graph problems).
A classic example is computing the Least Common Multiple (LCM) by reducing it to the Greatest Common Divisor (GCD) using the formula LCM(x, y) = (x * y) / GCD(x, y).
Other examples include transforming a maximization problem to a minimization problem, or reducing puzzle solving to state-space graph search problems.
هل الرمز P ≤ Q يعني أن المشكلة P أسهل من المشكلة Q؟ Does the notation P ≤ Q mean that problem P is easier than problem Q?
نعم، من الناحية النظرية يعني أن P ليست أصعب من Q، لأنه إذا كان لدينا حل لـ Q، فيمكننا استخدامه لحل P.
Yes, theoretically it implies that P is no harder than Q, because if we have an algorithm to solve Q, we can use it to solve P.
7 أشجار AVL
7 AVL Trees
أشجار AVL هي أشجار بحث ثنائية تحافظ على توازنها تلقائياً لضمان سرعة البحث.
AVL trees are self-balancing binary search trees that guarantee fast search times.
أشجار AVL هي أشجار بحث ثنائية (Binary Search Trees) تكون دائماً متوازنة إلى أقصى حد ممكن لشجرة ثنائية.
يتم الحفاظ على هذا التوازن من خلال تحويلات هيكلية من أربعة أنواع تسمى الدورانات (Rotations).
بفضل هذا التوازن الصارم، فإن جميع العمليات الأساسية (البحث، الإدراج، الحذف) في أشجار AVL تستغرق وقتاً لوغاريتمياً O(log n).
AVL trees are binary search trees that are always balanced to the extent possible for a binary tree.
The balance is maintained by structural transformations of four types called rotations.
Because of this strict balancing, all basic operations on AVL trees (search, insert, delete) are guaranteed to run in O(log n) time.
على عكس الكومة التي تهتم فقط بسيادة الأب، شجرة AVL تحافظ على ترتيب البحث (اليسار أصغر، اليمين أكبر) وتضمن أن فرق الارتفاع بين الشجرتين الفرعيتين لأي عقدة لا يتجاوز 1.
هذا يجعلها مثالية لعمليات البحث السريعة، بينما الكومة مثالية لطوابير الأولوية.
Unlike a heap which only cares about parental dominance, an AVL tree maintains the binary search property (left < parent < right) and strictly ensures that the height difference between left and right subtrees of any node is at most 1.
This makes it ideal for fast lookups, whereas heaps are optimized for priority queues.
| Heap | AVL Tree | |
|---|---|---|
| الترتيبOrdering | من أعلى لأسفل (الأب ≥ الأبناء)Top-down (Parent ≥ Children) | من اليسار لليمين (اليسار < الأب < اليمين)Left-to-right (Left < Parent < Right) |
| الوصول للعنصر الأكبرAccess to Maximum | O(1) - دائماً في الجذرO(1) - Always at root | O(log n) - أقصى اليمينO(log n) - Rightmost node |
| البحث عن عنصر عشوائيSearch for arbitrary element | O(n) - يتطلب بحث خطيO(n) - Requires linear search | O(log n)O(log n) |
متى نفضل استخدام شجرة AVL ومتى نفضل استخدام الكومة؟ When do we prefer using an AVL tree, and when do we prefer a Heap?
نستخدم شجرة AVL عندما نحتاج إلى بحث سريع عن أي عنصر (O(log n)) أو طباعة العناصر مرتبة. نستخدم الكومة عندما نحتاج فقط للوصول السريع للعنصر الأكبر/الأصغر (O(1)) كما في طوابير الأولوية.
We use an AVL tree when we need fast arbitrary lookups (O(log n)) or to traverse elements in sorted order. We use a Heap when we only need fast access to the maximum/minimum element (O(1)) as in priority queues.