تصنيف كومة ضعيف

تمت كتابة هذه المقالة بدعم من إديسون.

نحن منخرطون في إنشاء برامج مدمجة بالإضافة إلى تطوير تطبيقات الويب والمواقع .

نحن نحب نظرية الخوارزميات! ؛-)

كومة ضعيفة

التقليل من عدد المقارنات

أحفاد شعوذة

بناء كومة ضعيفة

1. إذا كان لدى السليل نسله ، فقم بتبديل الشجرة الفرعية اليسرى واليمنى (أي التبديل 0/1 في صفيف BIT لهذا العنصر).
2. تبادل قيم عقدة السليل والعقدة السلف.

تحليل كومة ضعيفة

ترتيب كومة ضعيف :: ترتيب كومة ضعيف

• I. :
  • I.1. -.
  • I.2. «» .
  • I.3. .
  • I.4. , :
    • I.4.. ( ⇔ ) , .
    • I.4.. «» .
• II. , :
  • II.1. .
  • II.2. . .
  • II.3. , . :
    • II.3.. .
    • II.3.. , .
    • II.3.. , , :
      • II.3.c. 1. نقوم بتبديل الشجرة الفرعية (اليسرى - اليمنى) مع المتحدرين للعقدة التي يوجد فيها السليل الأيسر الحالي.
      • II.3.c.2. نغير جذر الكومة والعقدة مع الطفل الأيسر الحالي.
  • II.4. في جذر الكومة الضعيفة هو مرة أخرى العنصر الأقصى للجزء المتبقي غير المصنف من الصفيف. نعود إلى الفقرة II.1 ونكرر العملية حتى يتم فرز جميع العناصر.

كود C ++

#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
  if (wheap[i] < wheap[j]) {//""  ?
    //  ,   
    //( "",   "")
    TOGGLEFLAG(r, j);
    //  ""  
    swap(wheap[i], wheap[j]);
  }
}

void WeakHeap::WeakHeapSort() {
  int n = Size();
  if(n > 1) {
		
    int i, j, x, y, Gparent;
    int s = (n + 7) / 8;
    unsigned char * r = new unsigned char [s];
		
    //  ,    
    // "",   ""
    for(i = 0; i < n / 8; ++i) r[i] = 0;
		
    //   
    for(i = n - 1; i > 0; --i) {
      j = i;
      //    , 
      //   ""  
      while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
      //       ""  
      Gparent = j >> 1;
      //  ,   
      //   ""
      WeakHeapMerge(r, Gparent, i);
    }
		
    //      -->
    //  -->    
    for(i = n - 1; i >= 2; --i) {
      //      
      //       
      swap(wheap[0], wheap[i]);
      x = 1;
      //    "" 
      while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
      //  ""     
      //        
      while(x > 0) {
        WeakHeapMerge(r, 0, x);
        x >>= 1;
      }
    }
    //  -   
    //    
    swap(wheap[0], wheap[1]);
    delete[] r;
  }
}

تعقيد الذاكرة الزائدة

تعقيد الوقت

غربلة كاملة

كومة ذات الحدين

خوارزمية سرية

1. لا يوجد "ضعف" ، إنها شجرة فرز كاملة (غير ثنائية) يتم فيها تحقيق مبدأ "أي والد أكبر من أي من نسله" والحفاظ عليه.
2. في جميع المراحل ، لا نقارن النسل ليس مع أسلافهم ، ولكن مع آبائهم المباشرين.
3. ما يشبه تبادل القيم بين السليل والسلف + تبادل الأماكن من الشجرة الفرعية في السليل - اتضح أنه تبادل النسبة نفسها (السليل / الأصل). إذا كانت العقدة الأصلية أصغر من السليل بالقيمة ، يصبح الأصل نفسه السليل ، ويصبح السليل الأصل.

في السلسلة التالية

المراجع

مقالات سلسلة:

• تطبيق Excel AlgoLab.xlsm
• أنواع التبادل
• أنواع الإدراج
• فرز حسب التحديد
  • أنواع الكومة: N-Pyramids
  • أنواع الكومة: أرقام ليوناردو
  • نوع الكومة: كومة ضعيفة
  • أنواع الحفريات: شجرة ديكارتية
  • فرز كومة أخرى: كومة مرآة ، كومة صغيرة ، غربلة من أسفل إلى أعلى
  • أنواع الكومة: Jung Heap
• دمج الأنواع
• فرز حسب التوزيع
• الفرز الهجين