TechCodeview

في هذه المقالة، سنناقش خوارزمية Heapsort. يقوم فرز الكومة بمعالجة العناصر عن طريق إنشاء الكومة الصغيرة أو الكومة القصوى باستخدام عناصر المصفوفة المحددة. يمثل Min-heap أو max-heap ترتيب المصفوفة التي يمثل فيها العنصر الجذر الحد الأدنى أو الحد الأقصى لعنصر المصفوفة.

ينفذ فرز الكومة بشكل متكرر عمليتين رئيسيتين -

• قم ببناء كومة H باستخدام عناصر المصفوفة.
• قم بحذف العنصر الجذري للكومة المتكونة في 1 بشكل متكرر^شارعمرحلة.

قبل معرفة المزيد عن نوع الكومة، دعونا نرى أولاً وصفًا مختصرًا له كومة.

ما هي الكومة؟

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

ما هو نوع الكومة؟

Heapsort هي خوارزمية فرز شائعة وفعالة. يتمثل مفهوم فرز الكومة في إزالة العناصر واحدًا تلو الآخر من جزء الكومة من القائمة، ثم إدراجها في الجزء الذي تم فرزه من القائمة.

Heapsort هي خوارزمية الفرز في المكان.

مثال لخريطة جافا

الآن دعونا نرى خوارزمية فرز الكومة.

خوارزمية

 HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End 

بيلد ماكس هيب(arr)

 BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End 

ماكس هيبيفي (arr،i)

 MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End 

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

الآن دعونا نرى عمل خوارزمية Heapsort.

في فرز الكومة، هناك مرحلتان أساسيتان لفرز العناصر. باستخدام خوارزمية فرز الكومة، فهي كما يلي -

• تتضمن الخطوة الأولى إنشاء كومة من خلال ضبط عناصر المصفوفة.
• بعد إنشاء الكومة، قم الآن بإزالة العنصر الجذر للكومة بشكل متكرر عن طريق نقله إلى نهاية المصفوفة، ثم قم بتخزين بنية الكومة مع العناصر المتبقية.

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

أولاً، علينا إنشاء كومة من المصفوفة المحددة وتحويلها إلى كومة قصوى.

بعد تحويل الكومة المحددة إلى الكومة القصوى، تكون عناصر المصفوفة -

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

بعد تبديل عنصر الصفيف 89 مع أحد عشر، وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف 81 مع 54 وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف 76 مع 9 وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف 54 مع 14 وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف 22 مع أحد عشر وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف 14 مع 9 وتحويل الكومة إلى أقصى كومة، عناصر المصفوفة هي -

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

بعد تبديل عنصر الصفيف أحد عشر مع 9, عناصر المصفوفة هي -

اسم مدينة في امريكا

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

بعد الانتهاء من الفرز، عناصر المصفوفة هي -

الآن، تم فرز المصفوفة بالكامل.

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

الآن، دعونا نرى التعقيد الزمني لفرز الكومة في أفضل الحالة، والحالة المتوسطة، والحالة الأسوأ. سنرى أيضًا مدى تعقيد مساحة Heapsort.

1. تعقيد الوقت

أفضل تعقيد للحالة -ويحدث ذلك عندما لا يكون هناك حاجة للفرز، أي أن المصفوفة قد تم فرزها بالفعل. أفضل تعقيد زمني لنوع الكومة هو يا (سجل ن). متوسط ​​تعقيد الحالة -يحدث ذلك عندما تكون عناصر المصفوفة في ترتيب مختلط لا تصاعدي بشكل صحيح ولا تنازلي بشكل صحيح. متوسط ​​التعقيد الزمني للحالة لفرز الكومة هو يا (ن سجل ن). أسوأ حالة تعقيد -يحدث ذلك عندما يلزم فرز عناصر المصفوفة بترتيب عكسي. هذا يعني أنه يجب عليك فرز عناصر المصفوفة بترتيب تصاعدي، ولكن عناصرها بترتيب تنازلي. أسوأ تعقيد زمني لنوع الكومة هو يا (ن سجل ن).

التعقيد الزمني لفرز الكومة هو يا (سجل ن) في الحالات الثلاث (أفضل حالة، ومتوسطة، وأسوأ حالة). ارتفاع الشجرة الثنائية الكاملة التي تحتوي على n من العناصر هو هادئ.

2. تعقيد الفضاء

• التعقيد المكاني لفرز الكومة هو O(1).

تنفيذ Heapsort

الآن، دعونا نرى برامج نوع Heap في لغات البرمجة المختلفة.

برنامج: اكتب برنامجًا لتنفيذ فرز الكومة بلغة C.

 #include /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here &apos;i&apos; is the index of root node in array a[], and &apos;n&apos; is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i &gt;= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are - 
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>