Heaps, Heapsort & Problem Reduction Heaps, Heapsort و Problem Reduction (اختزال المشاكل)

Part II of Transform-and-Conquer. Mastering data structures that bridge the gap between trees and arrays, and solving problems by transforming them into ones we already know. الجزء الثاني من "التحويل والسيطرة". إتقان هياكل البيانات التي تربط بين الأشجار والمصفوفات، وحل المشاكل عن طريق تحويلها إلى مشاكل نعرف حلها مسبقاً.

Representation Change Representation Change Heap Property Heap Property Priority Queues Priority Queues Reductions Reductions

Heaps: The Binary Tree in an Array Heaps: الشجرة الثنائية داخل مصفوفة

Definition التعريف

A Heap is a binary tree with two critical properties: الـ Heap هي شجرة ثنائية تتمتع بخاصيتين حاسمتين:

  • Structural Property: It is Essentially Complete. All levels are full except possibly the last, which is filled from left to right. This allows implementation as an ARRAY. الخاصية الهيكلية: هي Essentially Complete (شبه كاملة). جميع المستويات ممتلئة ما عدا الأخير، الذي يُملأ من اليسار إلى اليمين. هذا يسمح بتنفيذها كمصفوفة (ARRAY).
  • Parental Dominance: The key at every node is $\ge$ (or $\le$ for min-heap) the keys of its children. هيمنة الوالد (Parental Dominance): المفتاح في كل عقدة هو $\ge$ (أو $\le$ في الـ min-heap) مفاتيح أبنائها.
10
5
2
1
7

Array Representation تمثيل المصفوفة

10
5
7
2
1
12345

Heap Construction بناء الـ Heap (Heap Construction)

The "Heapify" Process عملية "Heapify"

We don't insert elements one by one ($O(n \log n)$). Instead, we dump data into an array and fix it Bottom-Up. نحن لا ندرج العناصر واحداً تلو الآخر ($O(n \log n)$). بدلاً من ذلك، نضع البيانات في مصفوفة ونصلحها بطريقة من الأسفل للأعلى (Bottom-Up).

  1. Start at the last parent node (index $\lfloor n/2 \rfloor$). ابدأ عند آخر عقدة أب (المؤشر $\lfloor n/2 \rfloor$).
  2. Check if the parent dominates its children. تحقق مما إذا كان الأب يهيمن على أبنائه.
  3. If not, Swap with the larger child (sift down). إذا لم يكن كذلك، بَدّل (Swap) مع الابن الأكبر (الغربلة لأسفل / sift down).
  4. Move backwards to index 1. تحرك للخلف حتى المؤشر 1.
Efficiency: $O(n)$ الكفاءة: $O(n)$

Surprisingly, building a heap is linear time, not log-linear. بشكل مفاجئ، بناء الـ heap يتم في وقت خطي، وليس لوغاريتمي-خطي.

Heapsort: The 2-Stage Algorithm Heapsort: الخوارزمية ذات المرحلتين

1

Stage 1: Construction المرحلة 1: البناء

Construct a heap from the given array using the Bottom-Up approach. بناء الـ heap من المصفوفة المعطاة باستخدام نهج Bottom-Up.


Cost: $O(n)$ Cost: $O(n)$
2

Stage 2: Root Deletion المرحلة 2: حذف الجذر

1. Swap Root (Max) with Last Element.
2. Decrease heap size by 1.
3. Sift down the new root.
4. Repeat $n-1$ times. 1. بدل الجذر (الأكبر) مع آخر عنصر.
2. قلل حجم الـ heap بمقدار 1.
3. غربل الجذر الجديد للأسفل.
4. كرر العملية $n-1$ مرة.

Cost: $O(n \log n)$ Cost: $O(n \log n)$
Total Complexity: $O(n \log n)$ التعقيد الكلي: $O(n \log n)$

Space Complexity: $O(1)$ (In-place) تعقيد المساحة: $O(1)$ (In-place)

Problem Reduction اختزال المشكلة (Problem Reduction)

"If you can't solve a problem, transform it into one you can solve." "إذا لم تتمكن من حل المشكلة، حولها إلى مشكلة تستطيع حلها."

LCM via GCD المضاعف المشترك الأصغر (LCM) عبر GCD

Finding the Least Common Multiple (LCM) is hard. Finding GCD (Euclid's) is easy. إيجاد المضاعف المشترك الأصغر (LCM) صعب. إيجاد القاسم المشترك الأكبر (GCD) باستخدام إقليدس سهل.

LCM(u, v) = (u * v) / GCD(u, v)

Counting Paths عد المسارات (Counting Paths)

Count paths of length $n$ in a graph? Reduce it to Matrix Multiplication. Compute $A^n$ (Adjacency Matrix to power $n$). عد المسارات بطول $n$ في رسم بياني؟ حولها إلى ضرب المصفوفات. احسب $A^n$ (مصفوفة المجاورة للقوة $n$).

Linear Programming البرمجة الخطية (Linear Programming)

Many optimization problems (Network Flow, Knapsack) can be reduced to a standard Linear Programming model and solved using Simplex. العديد من مشاكل التحسين (تدفق الشبكات، Knapsack) يمكن تحويلها إلى نموذج برمجة خطية قياسي وحلها باستخدام Simplex.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Heap vs BST فخ: Heap مقابل BST

A Heap is NOT a Binary Search Tree.
BST: Left < Parent < Right.
Heap: Parent > Children (Left AND Right).
Heaps are ordered top-to-bottom,
BSTs left-to-right. Don't confuse them! الـ Heap ليست شجرة بحث ثنائية (BST).
BST: اليسار < الأب < اليمين.
Heap: الأب > الأبناء (اليسار واليمين).
الـ Heaps مرتبة من الأعلى للأسفل،
والـ BSTs من اليسار لليمين. لا تخلط بينهما!

TRAP: Array Indices فخ: فهارس المصفوفات (Indices)

In algorithm theory, arrays often start at index 1 for easier math (Left child = $2i$, Right = $2i+1$).
In C++/Java, they start at 0 (Left = $2i+1$, Right = $2i+2$). Check the context of the question! في نظرية الخوارزميات، غالباً ما تبدأ المصفوفات عند المؤشر 1 لسهولة الحساب (الابن الأيسر = $2i$، الأيمن = $2i+1$).
في C++/Java، تبدأ عند 0 (اليسار = $2i+1$، اليمين = $2i+2$). تحقق من سياق السؤال!

SECRET: Construction Speed سر: سرعة البناء

Constructing a heap using `HeapInsert` $n$ times takes $O(n \log n)$. Using the Bottom-Up approach takes $O(n)$.
This linear time construction is the "secret sauce" of Heapsort efficiency. بناء الـ heap باستخدام `HeapInsert` لـ $n$ مرات يستغرق $O(n \log n)$. استخدام نهج Bottom-Up يستغرق $O(n)$.
هذا الوقت الخطي هو "السر" وراء كفاءة Heapsort.

KEY CONCEPT: Reduction Direction مفهوم مفتاحي: اتجاه الاختزال

Always reduce the Unknown problem TO the Known problem.
Correct: "I can solve LCM by reducing it to GCD."
Incorrect: "I can solve GCD by reducing it to LCM." دائماً اختزل المشكلة المجهولة إلى المشكلة المعروفة.
صحيح: "يمكنني حل LCM عن طريق اختزاله إلى GCD."
خطأ: "يمكنني حل GCD عن طريق اختزاله إلى LCM."