كومة منحرفة

عندما نرغب في دمج كومتين منحرفتين، يمكننا استخدام عملية مشابهة لعملية دمج كومتين يساريتين :

• قارن جذور كومتين؛ ليكن p الكومة ذات الجذر الأصغر، وq الكومة الأخرى. وليكن r اسم الكومة الجديدة الناتجة.
• ليكن جذر r هو جذر p (الجذر الأصغر)، وليكن الفرع الأيمن لـ r هو الفرع الأيسر لـ p.
• الآن، احسب الشجرة الفرعية اليسرى لـ r عن طريق دمج الشجرة الفرعية اليمنى لـ p مع q بشكل متكرر.

template < class T , class CompareFunction > SkewNode < T >* CSkewHeap < T , CompareFunction >:: Merge ( SkewNode < T >* root_1 , SkewNode < T >* root_2 ) { SkewNode < T >* firstRoot = root_1 ; SkewNode < T >* secondRoot = root_2 ;إذا كان ( firstRoot == NULL ) فأرجع secondRoot ؛وإلا إذا كان ( secondRoot == NULL ) فأرجع firstRoot ؛إذا كانت نتيجة مقارنة المفتاحين `firstRoot` و` secondRoot` باستخدام الدالة ` sh_compare- > Less` صحيحة ، فسيتم تنفيذ ما يلي : `SkewNode <T> * tempHeap = firstRoot- > rightNode ; firstRoot- > rightNode = firstRoot- > leftNode ; firstRoot- > leftNode = Merge ( secondRoot , tempHeap ) ; return firstRoot ; } ` وإلا ، فسيتم إرجاع نتيجة دمج المفتاحين ` secondRoot` و` firstRoot` .

قبل:

بعد

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

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

إضافة قيمة إلى كومة مائلة يشبه دمج شجرة ذات عقدة واحدة مع الشجرة الأصلية.

يمكن إزالة القيمة الأولى في كومة عن طريق إزالة الجذر ودمج الأشجار الفرعية التابعة له.

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

data SkewHeap a = Empt | Node a ( SkewHeap a ) ( SkewHeap a )singleton :: Ord a => a -> SkewHeap a singleton x = Node x Empty Emptyاتحاد :: ترتيب أ = > كومة مائلة أ -> كومة مائلة أ - > كومة مائلة أ فارغة ` اتحاد` t2 = t2 t1 ` اتحاد` فارغة = t1 t1 @ ( عقدة x1 l1 r1 ) ` اتحاد` t2 @ ( عقدة x2 l2 r2 ) | x1 < = x2 = عقدة x1 ( t2 ` اتحاد` r1 ) l1 | خلاف ذلك = عقدة x2 ( t1 ` اتحاد` r2 ) l2إدراج :: Ord a => a -> SkewHeap a -> SkewHeap a إدراج x كومة = singleton x ` union ` كومةextractMin :: Ord a => SkewHeap a -> Maybe ( a , SkewHeap a ) extractMin Empty = Nothing extractMin ( Node x l r ) = Just ( x , l ` union ` r )