بنية بيانات الكومة: ما هي الكومة؟ الحد الأدنى والحد الأقصى للكومة (مثال)

ما هي الكومة؟

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

لماذا تحتاج إلى بنية بيانات الكومة؟

فيما يلي الأسباب الرئيسية لاستخدام بنية بيانات الكومة:

  • تسمح بنية بيانات الكومة بالحذف والإدراج في الوقت اللوغاريتمي - O(log2ن).
  • يتم تصميم البيانات الموجودة في الشجرة بترتيب معين. إلى جانب تحديث أو الاستعلام عن أشياء مثل الحد الأقصى أو الأدنى، يمكن للمبرمج العثور على علاقات بين الوالدين والنسل.
  • يمكنك تطبيق مفهوم طراز كائن المستند لمساعدتك في فهم بنية بيانات الكومة.

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

بنية بيانات الكومة لديها العديد من الاختلافات algorithms للتعامل مع عمليات الإدراج وإزالة العناصر في بنية بيانات الكومة، بما في ذلك قائمة انتظار الأولوية، والكومة الثنائية، والكومة ذات الحدين، و نوع كومة.

  • طابور الأولوية: إنها بنية بيانات مجردة تحتوي على كائنات ذات أولوية. كل كائن أو عنصر له أولوية مرتبة مسبقًا له. ولذلك، فإن الكائن أو العنصر المعين له أولوية أعلى هو الحصول على الخدمة قبل الباقي.
  • كومة ثنائية: الأكوام الثنائية مناسبة للكومة البسيطة operaعمليات مثل الحذف والإدراج.
  • كومة ذات الحدين: تتكون الكومة ذات الحدين من سلسلة من مجموعات الأشجار ذات الحدين التي تشكل الكومة. شجرة الكومة ذات الحدين ليست شجرة عادية كما تم تعريفها بدقة. إجمالي عدد العناصر في شجرة ذات الحدين يمتلك دائمًا 2n العقد.
  • نوع كومة: على عكس معظم الفرز algorithms، يستخدم فرز الكومة مساحة O(1) لفرزه operaنشوئها. إنها خوارزمية فرز قائمة على المقارنة حيث يتم الفرز بترتيب متزايد عن طريق تحويله أولاً إلى كومة قصوى. يمكنك إلقاء نظرة على Heapsort باعتباره upgradeد شجرة البحث الثنائية الجودة.

عادةً ما تستخدم بنية بيانات الكومة استراتيجيتين. للإدخال 12 – 8 – 4 – 2 و 1

  • Min Heap – القيمة الأقل في الأعلى
  • ماكس كومة - أعلى قيمة في الأعلى

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

كومة دقيقة

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

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

مثال على الحد الأدنى من الكومة

مثال على الحد الأدنى من الكومة

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

لنفترض أنك قمت بتخزين العناصر في Array Array_N[12,2,8,1,4]. كما ترون من المصفوفة، فإن العنصر الجذر ينتهك أولوية Min Heap. للحفاظ على خاصية Min Heap، عليك تنفيذ min-heapify operaيمكنك تبديل العناصر حتى يتم استيفاء خصائص الحد الأدنى للكومة.

ماكس كومة

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

فيما يلي بعض الطرق لتنفيذ Java Max Heap

  • يضيف (): ضع عنصرًا جديدًا في الكومة. إذا كنت تستخدم مصفوفة، فستتم إضافة الكائنات في نهاية المصفوفة، بينما في الشجرة الثنائية، تتم إضافة الكائنات من الأعلى إلى الأسفل ثم بعد ذلك من اليسار إلى اليمين.
  • يزيل (): تتيح لك هذه الطريقة إزالة العنصر الأول من قائمة المصفوفات. وبما أن العنصر المضاف حديثًا لم يعد الأكبر، فإن طريقة Sift-Down تدفعه دائمًا إلى موقعه الجديد.
  • غربلة للأسفل (): شركات هذه الطريقةares كائن جذر إلى فرعه ثم يدفع العقدة المضافة حديثًا إلى موضعها الصحيح.
  • غربلة (): إذا كنت تستخدم طريقة الصفيف لإضافة عنصر مدرج حديثًا إلى صفيف، فإن طريقة Sift-Up تساعد العقدة المضافة حديثًا على الانتقال إلى موضعها الجديد. تتم أولاً مقارنة العنصر المدرج حديثًا بالعنصر الأصلي عن طريق محاكاة بنية بيانات الشجرة.

    تطبيق الصيغة Parent_Index=Child_Index/2. تستمر في القيام بذلك حتى يصبح الحد الأقصى للعنصر في مقدمة المصفوفة.

الكومة الأساسية Operaستعقد

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

  • - ابحث عن عنصر في الكومة.
  • إدراج - إضافة طفل جديد إلى الكومة.
  • حذف - حذف عقدة من الكومة.

إنشاء أكوام

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

لذلك دعونا نبدأ في إنشاء Min-heap باستخدام طريقة Willaim عن طريق إدراج القيم 12,2,8,1،4،XNUMX،XNUMX وXNUMX في الكومة. يمكنك بناء الكومة باستخدام عناصر n من خلال البدء بكومة فارغة ثم ملؤها على التوالي بعناصر أخرى باستخدام وقت O (nlogn).

إنشاء أكوام

  • Heapify: في خوارزمية الإدراج، مما يساعد على إدراج العناصر في الكومة. يتم اتباع عمليات التحقق، سواء تم تمييز بنية بيانات كومة الخاصية.

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

  • الدمج: نظرًا لأن لديك كومتين لدمجهما في كومة واحدة، استخدم أكوام الدمج لجلب القيم من الكومتين معًا. ومع ذلك، لا تزال الأكوام الأصلية محفوظة.

فحص أكوام

يشير فحص الكومة إلى التحقق من عدد العناصر في بنية بيانات الكومة والتحقق مما إذا كانت الكومة فارغة.

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

  • المقاس - إرجاع حجم أو طول الكومة. يمكنك معرفة عدد العناصر مرتبة.
  • فارغ - إذا كانت الكومة فارغة، فإنها تُرجع TRUE أخرىwise، تقوم بإرجاع FALSE.

هنا، تقوم بطباعة جميع العناصر الموجودة في ملف الأولويةس حلقة ثم التحقق من أن الأولوية Q ليست فارغة.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

استخدامات بنية بيانات الكومة

تعتبر بنية بيانات الكومة مفيدة في العديد من تطبيقات البرمجة في الحياة الواقعية مثل:

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

خصائص قائمة انتظار أولوية الكومة

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

خطوات تنفيذ قائمة انتظار الأولوية في Java

خطوات تنفيذ قائمة انتظار أولوية الكومة

فرز الكومة في JAVA مع مثال التعليمات البرمجية

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

الناتج

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

فرز الكومة في بيثون مع مثال التعليمات البرمجية

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

الناتج

[1, 3, 4, 7, 9]

التالي سوف تتعلم عن طريقة التنصيف

نبذة عامة

  • الكومة هي بنية بيانات شجرة متخصصة. دعونا نتخيل شجرة العائلة مع والديها وأطفالها.
  • بنية البيانات أكوام في جافا يسمح بالحذف والإدراج في الوقت اللوغاريتمي - O(log2ن).
  • أكوام في بايثون لديها مختلف algorithms للتعامل مع عمليات الإدراج وإزالة العناصر في بنية بيانات الكومة، بما في ذلك قائمة انتظار الأولوية، والكومة الثنائية، والكومة ذات الحدين، وفرز الكومة.
  • في بنية Min Heap، يكون للعقدة الجذرية قيمة مساوية أو أصغر من العناصر الفرعية الموجودة في تلك العقدة.
  • في بنية Max Heap، يكون للعقدة الجذرية (الأصل) قيمة تساوي أو أكبر من أبنائها في العقدة.
  • يشير فحص الكومة إلى التحقق من عدد العناصر في بنية بيانات الكومة والتحقق مما إذا كانت الكومة فارغة.