ما هي أسرع طريقة (من الناحية النظرية على الأقل) لفرز الكومة؟

Question

الكومة هي قائمة ينطبق عليها ما يلي:

l[i] <= l[2*i] && l[i] <= [2*i+1]

ل 0 <= i < len(list)

أنا أبحث عن الفرز في المكان.

Answer 1

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

إذا كنت تشعر بالشجاعة، فيمكنك البدء في التنفيذ com.mousesort, ، وهو أسرع من كومة الفرز للبيانات التي تم فرزها تقريبًا.

Answer 2

مجرد استخدام نوع الكومة.إنه في مكانه.سيكون هذا هو الاختيار الأكثر طبيعية.

يمكنك أيضًا استخدام الكومة الخاصة بك كما هي وفرزها باستخدام خوارزمية أخرى.بعد ذلك تقوم بإعادة بناء الكومة الخاصة بك من القائمة التي تم فرزها.يعد Quicksort مرشحًا جيدًا لأنه يمكنك التأكد من أنه لن يتم تشغيله بترتيب O(n²) الأسوأ لمجرد أن الكومة الخاصة بك قد تم فرزها مسبقًا بالفعل.

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

Answer 3

يبدو فرز الكومة في مكانها بمثابة وظيفة نوع كومة.

أفترض أن الذاكرة مقيدة، ربما تطبيق مضمن؟

Answer 4

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

Answer 5

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

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

هذه ليست الطريقة الأسرع على الإطلاق للفرز غير المكاني كما يوضح ديفيد ماكاي هنا - يمكنك القيام بعمل أفضل من خلال وضع عنصر من المرجح أن يكون الأصغر في أعلى الكومة بدلاً من عنصر من الصف السفلي.

التعقيد الزمني هو أسوأ حالة T(n.log n) - التكرارات n مع احتمال تسجيل n (ارتفاع الكومة) تمر عبر حلقة while.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

اقرأ العناصر الموجودة أعلى الكومة واحدًا تلو الآخر.في الأساس ما لديك بعد ذلك هو نوع الكومة.