خوارزمية فرز الكومة (مع الكود في Python C++)

ما هي خوارزمية فرز الكومة؟

تعد عملية فرز الكومة واحدة من أكثر خوارزميات الفرز شيوعًا وسرعة. وهي مبنية على بنية بيانات الشجرة الثنائية الكاملة. سنبحث عن العنصر الأقصى ونضعه في أعلى الكومة القصوى. وسنضعه في العقدة الرئيسية للشجرة الثنائية.

لنفترض أنه تم إعطاء مصفوفة، البيانات = [10,5،7، 9، 4، 11، 45، 17، 60، XNUMX].

في المصفوفة، إذا كان الفهرس i-th (i=0,1,2,3 …) هو العقدة الأصلية، فإن (2i+1) و(2i+2) سيكونان العقدة الفرعية اليمنى واليسرى. سيبدو إنشاء شجرة ثنائية كاملة باستخدام هذه المصفوفة كما يلي:

سنجري عملية التجميع من البداية إلى النهاية للمصفوفة. في البداية، إذا قمنا بتحويل المصفوفة إلى شجرة، فستبدو كما هو موضح أعلاه. يمكننا أن نرى أنها لا تحتفظ بأي خاصية كومة (min-heap أو max heap). سنحصل على المصفوفة المرتبة من خلال إجراء عملية التجميع لجميع العقد.

تطبيق فرز الكومة

إليك بعض استخدامات خوارزمية فرز الكومة:

يحتاج إنشاء "قوائم الانتظار ذات الأولوية" إلى فرز الكومة. لأن heapsort يحافظ على فرز العنصر بعد إجراء كل عملية إدراج.
بنية بيانات الكومة فعالة في العثور على k^th أكبر عنصر في مجموعة معينة.
يستخدم Linux Kernel فرز الكومة كإعداد افتراضي خوارزمية الفرز حيث أن لها تعقيدًا فضائيًا قدره O (1).

إنشاء فرز الكومة مع المثال

هنا، سوف نقوم بإنشاء كومة قصوى من الشجرة الثنائية الكاملة التالية.

العقد الورقية هي 17 و60 و4 و11 و45. ليس لها أي عقد فرعية. ولهذا السبب فهي عقد ورقية. لذا، سنبدأ طريقة heapify من العقدة الأصلية الخاصة بها. فيما يلي الخطوات:

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

العقدة الأصلية هنا هي 9. والعقدتان الفرعيتان هما 17 و60. وبما أن 60 هي الأكبر، فسيتم تبديل 60 و9 للحفاظ على كومة ماكس.

الخطوة 2) الآن، تم تكديس الشجرة الفرعية الموجودة في أقصى اليسار. العقدة الأصلية التالية هي 7. هذه العقدة الأصلية لديها عقدتان فرعيتان، والعقدة الأكبر هي 45. لذا، سيتم تبديل 45 و7.

الخطوة 3) تحتوي العقدتان 60 و4 على العقدة الأصلية 5. وبما أن "5" أصغر من العقدة الفرعية 60، فسيتم تبديلها.

الخطوة 4) الآن، العقدة 5 بها العقدة الفرعية 17,9. هذا لا يحافظ على خاصية الحد الأقصى للكومة. لذلك، سيتم استبدال 5 بـ 17.

الخطوة 5) سيتم تبديل العقدة 10 بالعقدة 60، ثم بالعقدة 17. ستبدو العملية كما يلي.

الخطوة 6) حتى الخطوة 5، أنشأنا الحد الأقصى للكومة. كل عقدة أصل أكبر من عقدها الفرعية. العقدة الجذرية لها القيمة القصوى (60).

ملحوظة: لإنشاء المصفوفة التي تم فرزها، نحتاج إلى استبدال العقدة ذات القيمة القصوى بالعقدة اللاحقة لها.

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

الخطوة 7) بما أنه تمت إزالة 60، فإن القيمة القصوى التالية هي 45. سنقوم بعملية "استخراج الحد الأقصى" مرة أخرى من العقدة 45.

هذه المرة سوف نحصل على 45 ونستبدل العقدة الجذرية بالعقدة التي تليها 17.

نحن بحاجة إلى أداء "استخراج ماكس"حتى يتم فرز جميع العناصر.

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

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

الكومة الثنائية هي نوع من الاكتمال شجرة ثنائية بنية البيانات. في هذا النوع من بنية الشجرة، تكون العقدة الأصلية إما أكبر أو أصغر من العقد الفرعية. إذا كانت العقدة الأصلية أصغر، تسمى الكومة "Min Heap" وإذا كانت العقدة الأصلية أكبر، تسمى الكومة "Max Heap".

فيما يلي أمثلة على الحد الأدنى للكومة والحد الأقصى للكومة.

في الشكل أعلاه، إذا لاحظت "Min Heap"، فإن العقدة الأصلية تكون دائمًا أصغر من العقد التابعة لها. عند رأس الشجرة، يمكننا إيجاد القيمة الأصغر وهي 10.

وبالمثل، بالنسبة لـ "Max Heap"، تكون العقدة الأصلية دائمًا أكبر من العقد الفرعية. الحد الأقصى للعنصر موجود في العقدة الرئيسية لـ "Max Heap".

ما هو "Heapify"؟

"Heapify" هو مبدأ الكومة الذي يضمن موضع العقدة. في Heapify، تحافظ الكومة القصوى دائمًا على علاقة مع العقدة الأصلية والعقدة الفرعية، أي أن العقدة الأصلية ستكون أكبر من العقد الفرعية.

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

فيما يلي مثال لكيفية عمل heapify:

إضافة عقدة جديدة وتكوين كومة — إضافة عقدة جديدة وتكديسها

فيما يلي الخطوات اللازمة لـ heapify:

الخطوة 1) تمت إضافة العقدة 65 باعتبارها الفرع الأيمن للعقدة 60.

الخطوة 2) تحقق مما إذا كانت العقدة المضافة حديثًا أكبر من العقدة الأصلية.

الخطوة 3) نظرًا لأنها أكبر من العقدة الأصلية، فقد قمنا بتبديل الطفل المناسب مع العقدة الأصلية.

كيفية بناء الكومة

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

لنفترض أن المصفوفة تحتوي على إجمالي n من العناصر. إذا كان الفهرس "i" عبارة عن عقدة أصلية، فستكون العقدة اليسرى في الفهرس (2ط+1)، وستكون العقدة اليمنى في الفهرس (2ط+2). نحن نفترض أن فهرس المصفوفة يبدأ من 0.

باستخدام هذا، دعنا نخزن الحد الأقصى من البيانات في مصفوفة تشبه الشكل التالي:

التمثيل القائم على الصفيف لـ Max Heap — تمثيل قائم على المصفوفة للحجم الأقصى

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

فيما يلي الخطوات اللازمة لتكديس كومة قصوى:

الخطوة 1) ابدأ من العقدة الورقية.

الخطوة 2) العثور على الحد الأقصى بين الوالدين والأطفال.

الخطوة 3) قم بتبديل العقد إذا كانت العقدة الفرعية لها قيمة أكبر من العقدة الأصلية.

الخطوة 4) انتقل إلى مستوى واحد أعلى.

الخطوة 5) اتبع الخطوات 2,3,4،0،XNUMX حتى نصل إلى الفهرس XNUMX أو فرز الشجرة بأكملها.

فيما يلي الكود الزائف لعملية التكديس التكراري (الحد الأقصى للكومة):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

الكود الزائف لفرز الكومة

إليك الكود الزائف لخوارزمية فرز الكومة:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

مثال على رمز فرز الكومة في C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

الإخراج:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

مثال على رمز فرز الكومة في Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

الإخراج:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

تحليل تعقيد الوقت والمكان لفرز الكومة

هناك تعقيد زمني وتعقيد مكاني يمكننا تحليلهما لفرز الكومة. بالنسبة لتعقيد الوقت، لدينا الحالات التالية:

أفضل حالة
متوسط الحالة
الحالة الأسوأ

يتم تنفيذ الكومة على شجرة ثنائية كاملة. لذلك، في المستوى السفلي من الشجرة الثنائية، سيكون هناك الحد الأقصى لعدد العقد. إذا كان المستوى السفلي يحتوي على n من العقد، فإن المستوى أعلاه سيكون له n/2 من العقد.

في هذا المثال، يحتوي المستوى 3 على أربعة عناصر، والمستوى 2 يحتوي على عنصرين، والمستوى 1 يحتوي على عنصر واحد. إذا كان هناك إجمالي عدد n من العناصر، فسيكون الارتفاع أو المستوى الإجمالي سجل₂(ن). لذا، فإن إدراج عنصر واحد قد يستغرق الحد الأقصى من تكرارات Log(n).

عندما نريد أخذ القيمة القصوى من الكومة، نأخذ فقط العقدة الجذرية. ثم مرة أخرى، نقوم بتشغيل الكومة. تأخذ كل كومة سجل₂(ن) وقت. يستغرق استخراج الحد الأقصى وقتًا O(1).

أفضل تعقيد زمني للحالة لخوارزمية فرز الكومة

عندما يتم فرز جميع العناصر بالفعل في المصفوفة، سيستغرق الأمر وقتًا O(n) لبناء الكومة. لأنه إذا تم فرز القائمة فإن إدراج عنصر سيستغرق الوقت الثابت وهو O(1).

لذا، سيستغرق الأمر وقتًا O(n) لإنشاء الحد الأقصى أو الحد الأدنى للكومة في أفضل الأحوال.

متوسط تعقيد وقت الحالة لخوارزمية فرز الكومة

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

أسوأ حالة تعقيد زمني لخوارزمية فرز الكومة

على غرار الحالة المتوسطة، في أسوأ السيناريوهات، قد نضطر إلى إجراء عملية تكديس n مرة. ستستغرق كل عملية تكديس O(log(n)) من الوقت. لذا، فإن أسوأ تعقيد زمني سيكون يا (ن سجل (ن)).

تعقيد المساحة لخوارزمية فرز الكومة

إن فرز الكومة عبارة عن خوارزمية مصممة في المكان. وهذا يعني أنه لا توجد حاجة إلى ذاكرة إضافية أو مؤقتة لأداء المهمة. إذا رأينا التنفيذ، فسوف نلاحظ أننا استخدمنا swap () لأداء تبادل العقد. لم تكن هناك حاجة إلى قائمة أو مصفوفة أخرى. لذا، فإن تعقيد المساحة هو O(1).

قد ترغب: