الطوابير

6. الطوابير

يعرض هذا الفصل عدة بنى معطيات تُعرف باسم الطوابير (queues). والطابور (queue) بنية معطيات تُستخرج عناصرها بالترتيب الذي أُدرجت به، وهو ما يقابل بدقة المفهوم المعتاد للطابور. ويمكننا أيضًا إقران العناصر بأولويات، وفي هذه الحالة لا تُستخرج العناصر بعد ذلك بالترتيب الذي أُدرجت به. ويُسمى هذا طابور الأولوية (priority queue).

6.1 الطوابير الأمرية (imperative queues)

يعرض هذا القسم بنية معطيات للطوابير الأمرية مبنية على القوائم المترابطة. وتُعطى توقيعة هذه البنية في البرنامج 57 (انظر الصفحة التالية).

الفكرة كما يلي: إذا احتوى طابور q على العناصر 1، 2، 3، مُدرجة بهذا الترتيب، فإنه يُمثَّل بقائمة مترابطة دائرية يشير فيها كل عنصر إلى العنصر التالي له في الطابور، ويشير العنصر الأخير إلى الأول. ولكي نتمكن من إدراج العناصر وإزالتها في زمن ثابت، يكفي أن نحتفظ بمؤشر إلى العنصر الأخير في الطابور، وهنا العنصر 3. وبذلك تكون لدينا الحالة التالية:

وهكذا، لإدراج عنصر جديد، هو 4، يكفي إدراجه بعد 3، أي بين 3 و1، ثم نقل المؤشر إلى 4.

نصل إلى العنصر الأول، وهنا 1، بتتبع المؤشر الموجود في العنصر الأخير. ولإزالة العنصر الأول، يكفي أن نجعل العنصر الأخير يشير إلى العنصر الثاني، وهنا 2، الذي نحصل عليه بتتبع مؤشرين.

نبدأ بتعريف نوع ’acell لتمثيل خلايا القائمة المترابطة، بالطريقة المعتادة.

  type ’a cell = { elt : ’a; mutable next : ’a cell }

ثم نمثّل الطابور بمرجع إلى الخلية الأخيرة. وتنشأ مشكلة عند تمثيل الطابور الفارغ، الذي لا نريد أن يحتوي على أي خلايا قائمة على الإطلاق. لذلك نختار تمثيل الطابور بمرجع إلى قيمة من النوع ’acelloption، حيث يمثّل None الطابور الفارغ.

  type ’a t = ((’a cell) option) ref

تنفيذ الدالتين create وis_empty واضح.

  let create () =
    ref None
  let is_empty q =
    !q = None

إدراج عنصر

يتبع إدراج عنصر x في طابور q المخطط المذكور أعلاه. فإذا كان q فارغًا، ننشئ قائمة دائرية من عنصر واحد ونعدّل q بحيث يشير إلى هذا العنصر. ونستعمل هنا الإمكانية التي يتيحها OCaml لبناء قيمة دورية بواسطة letrec.

  let push x q = match !q with
    | None ->
        let rec c = { elt = x; next = c } in
        q := Some c

وإذا لم يكن q فارغًا، ننشئ خلية جديدة c تحتوي على x، ندرجها بين العنصرين الأخير والأول، ثم نعدّل q بحيث يشير إلى هذه الخلية الجديدة.

    | Some last ->
        let c = { elt = x; next = last.next } in
        last.next <- c;
        q := Some c

استخراج عنصر

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

  let pop q = match !q with
    | None ->
        invalid_arg "pop"

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

    | Some last when last.next == last ->
        q := None;
        last.elt

في الحالة العامة، عندما يحتوي q على عنصرين على الأقل، نبدأ بتحديد العنصر الأول في الطابور، first. ثم نزيله من القائمة المترابطة بجعل العنصر الأخير يشير إلى العنصر الثاني. والقيمة الواجب إرجاعها موجودة في الخلية first.

    | Some last ->
        let first = last.next in
        last.next <- first.next;
        first.elt

الكود الكامل معطى في البرنامج 58 (انظر الصفحة التالية).

التعقيد

من الواضح أن العمليات create وis_empty وpush وpop تُنفَّذ كلها في زمن ثابت. والطابور الذي يحتوي على N عنصرًا يشغل ثلاث كلمات لكل عنصر في الذاكرة (لكونه سجلًا بحقلين، هما elt وnext)، إضافة إلى كلمتين للمرجع.

6.2 الطوابير الدائمة (persistent queues)

في هذا القسم، نعرض بنية معطيات للطوابير الدائمة (persistent). وتُعطى توقيعة هذه البنية في البرنامج 59. ونرى، على وجه الخصوص، أن العمليتين push وpop تُعيدان نسخة معدَّلة من بنية المعطيات.

قد تتمثل فكرة ساذجة في تمثيل طابور بقائمة. لكن هذا الحل غير فعّال جدًا للأسف، لأنه سيتعين إمّا تنفيذ عملية الإدراج أو عملية الاستخراج في نهاية القائمة. ولتنفيذ هاتين العمليتين بكفاءة أكبر، تتمثل فكرة بسيطة في استعمال قائمتين لا قائمة واحدة. فالقائمة الأولى تحتوي على العناصر الموجودة في مقدمة الطابور، بالترتيب. والقائمة الثانية تحتوي على العناصر الموجودة في مؤخرة الطابور، بترتيب معكوس. وبهذه الطريقة، يتم الإدراج والاستخراج معًا عند رأس القائمة. وعلى سبيل المثال، قد يُمثَّل الطابور الذي يحتوي على العناصر 1، 2، 3، 4، 5، المُدرجة بهذا الترتيب، بالقائمتين [1;2] و[5;4;3]. غير أن الطابور قد يُمثَّل بالقدر نفسه بالقائمتين [1] و[5;4;3;2]، أو حتى بـ [1;2;3;4;5] و[]، وكلها تمثيلات مكافئة للطابور نفسه.

لذلك نعرّف نوع الطوابير الدائمة ببساطة كمرادف لزوج من القوائم.

  type ’a t = ’a list * ’a list

تمثّل القائمة الأولى مقدمة الطابور. وتمثّل الثانية مؤخرة الطابور. وتعريفا الطابور الفارغ empty والدالة is_empty واضحان.

  let empty = [], []

  let is_empty = function
    | [], [] -> true
    | _ -> false

لإدراج عنصر x، يكفي إضافته إلى رأس القائمة الثانية.

  let push x (o, i) =
    (o, x :: i)

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

  let pop = function
    | [], [] ->
        invalid_arg "pop"

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

    | x :: o, i ->
        x, (o, i)

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

    | [], i ->
        match List.rev i with
        | x :: o -> x, (o, [])

بما أن القائمة i ليست فارغة، فإن القائمة List.revi ليست فارغة أيضًا. وبدلًا من كتابة مطابقة نمط غير شاملة تُطلق تحذيرًا من المترجم، نذكر صراحةً أن حالة القائمة الفارغة لا يمكن أن تحدث.

        | [] -> assert false

الكود الكامل معطى في البرنامج 60.

التعقيد

من الواضح أن العمليتين is_empty وpush تُنفَّذان في زمن ثابت. غير أن العملية pop قد تكون كلفتها O(N) لطابور يحتوي على N عنصرًا. وهذا هو الحال عندما تكون جميع العناصر في مؤخرة الطابور بحيث يجب عكس القائمة. ومع ذلك، إذا نظرنا إلى متتالية من M عملية متعاقبة من push وpop، انطلاقًا من طابور فارغ، فإن الكلفة الإجمالية لا يمكن أن تتجاوز O(M). وفعلًا، قد يشارك كل عنصر في عملية عكس واحدة للقائمة على الأكثر. ومن ثمّ فإن للعملية pop كلفة مطفأة O(1). أما تعقيد المساحة فهو نفسه كما في حالة الطوابير الأمرية، بثلاث كلمات لكل عنصر من الطابور.

6.3 طوابير الأولوية الأمرية (imperative priority queues)

في هذا القسم والقسم التالي، سنتناول طوابير تُقرن فيها العناصر بأولويات. وفي مثل هذه الطوابير، المسماة طوابير الأولوية (priority queues)، تُزال العناصر بالترتيب الذي تحدده أولوياتها لا بالترتيب الذي أُدخلت به. ونعرض هنا بنية معطيات أمرية (imperative) لطوابير الأولوية، تُعطى توقيعتها في البرنامج 61 (انظر الصفحة التالية).

في هذه الواجهة، يتوافق مفهوم الصغر مع مفهوم الأولوية العليا. وخلافًا للطوابير العادية، نميّز هنا بين الوصول إلى العنصر الأول وإزالته باستعمال عمليتين منفصلتين. وذلك لأجل الكفاءة، كما سيُوضَّح لاحقًا. وبناءً على ذلك، تُعيد الدالة get_min العنصر ذا الأولوية الأعلى في الطابور، وتزيله الدالة remove_min.

لتنفيذ طابور أولوية فعّال، من الضروري استعمال بنية معطيات أكثر تعقيدًا من حالة الطوابير العادية. ويتمثل أحد الحلول في تنظيم العناصر في كومة (heap). والكومة شجرة ثنائية يحمل فيها العنصر المخزَّن عند كل عقدة أولوية أعلى من أولوية العنصرين الواقعين تحتها مباشرة. لذا يوجد العنصر ذو الأولوية الأعلى عند الجذر. وهكذا، قد يكون للكومة التي تحتوي على العناصر {3,7,9,12,21}، مرتبة حسب المقدار، الشكل التالي:

نلاحظ أن هناك أكوامًا أخرى تحتوي على العناصر نفسها. غير أنه، لأجل الكفاءة، يُفضَّل اختيار كومة ذات ارتفاع أدنى. والأكوام الممثَّلة بأشجار ثنائية كاملة (تُملأ فيها جميع المستويات عدا الأخير ربما) لها ارتفاع أدنى. ويتضح أنه يمكن تمثيل شجرة ثنائية كاملة بسهولة باستعمال مصفوفة. وتتمثل الفكرة في ترقيم عقد الشجرة من أعلى إلى أسفل ومن اليسار إلى اليمين، بدءًا من 0. وتُنتج نتيجة هذا الترقيم للكومة أعلاه التسميات التالية:

ويتيح هذا الترقيم تمثيل الكومة في مصفوفة من خمسة عناصر كما يلي:

بوجه عام، يشغل جذر الشجرة الخلية ذات الفهرس 0، ويُخزَّن جذرا الشجرتين الفرعيتين للعقدة المخزَّنة في الخلية i في الخليتين 2i + 1 و2i + 2 على التوالي. وبالعكس، يُخزَّن أب العقدة i في ⌊(i − 1)∕2⌋.

تبقى مشكلة واحدة: لا نعرف حجم طابور الأولوية مسبقًا، ومن ثمّ لا يمكننا تحديد الحجم الأقصى للمصفوفة بشكل مسبق. ويتمثل أحد الحلول الأنيقة في استعمال المصفوفات القابلة لتغيير الحجم. وقد عُرضت مثل هذه المصفوفات في القسم 4.1المصفوفات القابلة لتغيير الحجم (resizeable arrays). لذا يكفي عندئذ كتابة دالة تصنيف (functor) مُعامَلة ببنية للمصفوفات القابلة لتغيير الحجم. وتُعطى توقيعة لمثل هذه المصفوفات، هي ResizeableArray، في البرنامج 17، في بداية الفصل 4. وفيما يخص العناصر، نحتاج إلى نوع مزوَّد بترتيب كلي وقيمة افتراضية. وتُعطى التوقيعة المقابلة، وهي OrderedWithDummy، في البرنامج 62.

تأخذ دالة تصنيف طوابير الأولوية عندئذ الشكل التالي:

module Make(X: OrderedWithDummy)(A: ResizeableArray)
  : ImperativePriorityQueue with type elt = X.t =
struct

الوحدة X هي وحدة العناصر حينئذ، والوحدة A هي وحدة المصفوفات القابلة لتغيير الحجم.

والنوعان elt وt مرادفان على التوالي لـ X.t وeltA.t.

  type elt = X.t
  type t = elt A.t

في الواقع، ليست الكومة سوى مصفوفة قابلة لتغيير الحجم. وتبني الدالة create مصفوفة فارغة بواسطة A.make، وتختبر الدالة is_empty ما إذا كانت المصفوفة فارغة.

  let create () = A.make 0 X.dummy
  let is_empty h = A.length h = 0

تُعيد الدالة get_min جذر الكومة، إذا كان موجودًا، وترفع استثناءً في الحالة المعاكسة.

  let get_min h =
    if A.length h = 0 then invalid_arg "get_min";
    A.get h 0

الكود معطى في البرنامج 63.

إدراج عنصر

يتمثل إدراج عنصر x في كومة h في إضافة x إلى الشجرة التي تمثّل h مع الحفاظ على بنية الكومة. ويتمثل أحد الأساليب في إضافة x في أسفل اليمين ثم تحريكه صعودًا في الشجرة بالقدر اللازم. وفي تنفيذنا، يُختصر هذا إلى توسيع المصفوفة بخلية واحدة، وإدراج القيمة x فيها، ثم تحريك x صعودًا حتى يبلغ موضعه الصحيح. ولهذا نستعمل الخوارزمية التالية: إذا كان x أصغر من أبيه، نبادل القيمتين ونكرر.

على سبيل المثال، لنعاين مرة أخرى الكومة التالية:

ويُنفَّذ إدراج العنصر 1 في هذه الكومة في ثلاث خطوات:

نبدأ بكتابة دالة move_up تُدرج عنصرًا x في الكومة h، انطلاقًا من الموضع i. وتفترض هذه الدالة أن شجرة الجذر i، الناتجة عن وضع x عند i، هي كومة. وتعالج الدالة move_up أولًا الحالة التي يكون فيها i مساويًا 0، أي عندما نكون قد بلغنا الجذر. حينئذ يكفي إدراج x عند الموضع i.

  let rec move_up h x i =
    if i = 0 then
      A.set h i x

أما إذا كنا عند عقدة داخلية، فنحسب الفهرس fi لأب i والقيمة y المخزَّنة في هذه العقدة. وإذا كان y أكبر من x، يجب أن نحرّك x صعودًا مع تحريك y نزولًا إلى الموضع i. ثم نستدعي move_up استدعاءً تكراريًا انطلاقًا من fi.

    else
      let fi = (i - 1) / 2 in
      let y = A.get h fi in
      if X.compare y x > 0 then begin
        A.set h i y;
        move_up h x fi
      end

أما إذا كان y أصغر من x أو مساويًا له، فإن x عند موضعه النهائي، ويكفي تخزينه هناك.

      else A.set h i x

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

  let add x h =
    let n = A.length h in
    A.resize h (n + 1);
    move_up h x n

الكود معطى في البرنامج 63 (انظر الصفحة التالية).

إزالة أصغر عنصر

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

لنفترض، على سبيل المثال، أننا نريد إزالة أصغر عنصر من الكومة التالية:

نستبدل الجذر، وهو 1، بالعنصر الواقع في أسفل اليمين، وهو 8. ثم نجعل 8 ينزل حتى يبلغ موضعه. ولهذا نقارن 8 بجذري الشجرتين الفرعيتين a وb. فإذا كان a وb كلاهما أكبر من 8، يكتمل النزول. وإلا، نبادل 8 بالأصغر من العقدتين a وb، ونواصل النزول. وفي المثال، يُبادَل 8 على التوالي بـ 4 و5:

نبدأ بكتابة دالة تقارن عقدتين، معطاتين بفهرسيهما l وr، وتُعيد الأصغر منهما.

  let min h l r =
    if X.compare (A.get h r) (A.get h l) < 0 then r else l

بعد ذلك، نكتب دالة smallest_node تحدّد ما إذا كانت قيمة x، الواقعة عند العقدة i، بحاجة إلى النزول في الكومة أم لا. ولا تكون القيمة x هي قيمة العقدة i لأننا لا نعرف بعد ما إذا كان هذا سيكون موضعها النهائي. غير أن الدالة smallest_node تتصرّف كما لو كانت العقدة i تحمل القيمة x. وبناءً على ذلك، تأخذ الدالة smallest_node وسائط هي الكومة h والقيمة x والفهرس i. ونبدأ بحساب الابن الأيسر l للعقدة i.

  let smallest_node h x i =
    let l = 2 * i + 1 in

إذا لم تكن للعقدة i أي أبناء، نُعيد i.

    let n = A.length h in
    if l >= n then
      i

أما إذا كانت العقدة l جزءًا من الكومة، فنحدّد الفهرس j لأصغر ابن للعقدة i. ولهذا، من المناسب تحديد ما إذا كان الابن الأيمن r=l+1 موجودًا. فإن كان موجودًا، نقارن العقدتين l وr بالدالة min. وإلا، يكون الفهرس j مساويًا لـ l.

    else
      let r = l + 1 in
      let j = if r < n then min h l r else l in

وأخيرًا، نقارن قيمة العقدة j بقيمة x.

      if X.compare (A.get h j) x < 0 then j else i

يُنجَز النزول في الكومة بدالة تكرارية move_down تأخذ وسائط هي الكومة h والقيمة x التي تنزل والفهرس i للعقدة المرشَّحة. ونبدأ باستدعاء الدالة smallest_node لحساب الفهرس j الذي ينبغي أن يستقبل القيمة x.

  let rec move_down h x i =
    let j = smallest_node h x i in

إذا كان j=i، اكتمل النزول ويكفي تخزين القيمة x عند الفهرس i.

    if j = i then
      A.set h i x

وإلا، ننقل قيمة العقدة j صعودًا إلى العقدة i ثم نواصل النزول من j.

    else begin
      A.set h i (A.get h j);
      move_down h x j
    end

وتكون دالة إزالة أصغر عنصر من كومة h عندئذ كما يلي:

  let remove_min h =
    let n = A.length h - 1 in
    if n < 0 then invalid_arg "remove_min";
    let x = A.get h n in
    A.resize h n;
    if n > 0 then move_down h x 0

ننظر في ثلاث حالات: إذا كانت الكومة فارغة، نرفع استثناءً. ثم إذا كانت تحتوي على عنصر واحد فقط، ليس من الضروري استدعاء الدالة move_down. وأخيرًا، إذا كانت الكومة تحتوي على أكثر من عنصر واحد، يجدر تغيير حجم المصفوفة بـ A.resize. والكود الكامل معطى في البرنامجين 63 (انظر الصفحة 542) و64.

التعقيد

من الواضح أن للدوال create وis_empty وget_min كلفة ثابتة. أما في حالة الدالتين add وremove_min، فكلفتهما محدودة بارتفاع الكومة. وفعلًا، ننتقل في إحدى الحالتين من الأوراق نحو الجذر، وفي الأخرى من الجذر نحو الأوراق. وبما أن الكومة شجرة ثنائية كاملة، فإن ارتفاعها لوغاريتمي في عدد العناصر. لذا فإن للدالتين add وremove_min، في طابور أولوية يحتوي على N عنصرًا، كلفة O(log N). وثمة طريقة أبسط للنظر إلى الأمر تتمثل في ملاحظة أن الدالة move_up تقسم وسيطها i على اثنين عند كل استدعاء تكراري. ومن ثمّ لا يمكن استدعاؤها أكثر من O(log N) مرة. وبالمثل، تضرب الدالة move_down وسيطها في اثنين عند كل استدعاء تكراري، ومن ثمّ لا يمكن استدعاؤها أكثر من O(log N) مرة. وبالطبع، لا ينطبق كل هذا إلا بصورة مطفأة بحكم الاستدعاءات إلى resize، وهي مطفأة O(1)، كما بيّنّا في الفصل 4.

يعتمد تعقيد المساحة على تنفيذ المصفوفة القابلة لتغيير الحجم. فإذا استعملنا التنفيذ المعروض في بداية الفصل 4، حيث كان حجم المصفوفة يُضاعَف عند الحاجة إلى زيادته، فإن المصفوفة تحتوي على ضعف عدد العناصر المطلوب على الأكثر. ومن ثمّ يشغل طابور أولوية يحتوي على N عنصرًا 2N كلمة ذاكرة على الأكثر.

6.4 طوابير الأولوية الدائمة (persistent priority queues)

في هذا القسم، نعرض بنية معطيات لطوابير الأولوية الدائمة (persistent)، تُعطى توقيعتها في البرنامج 65.

كما في القسم السابق، نستعمل بنية معطيات الكومة، إلا أنها هنا ممثَّلة مباشرة بشجرة ثنائية. وخلافًا لحالة أشجار AVL، لا تُخزَّن أي معلومات إضافية في العقد لأغراض الموازنة. وسنرى لاحقًا أن لهذه الأكوام مع ذلك تعقيدًا لوغاريتميًا مطفأً. ونقول إن هذه الأشجار ذاتية الموازنة (self-balancing).

لذلك تأخذ دالة تصنيف طوابير الأولوية الدائمة الشكل التالي:

module Make(X: Ordered) :
  PersistentPriorityQueue with type elt = X.t =
struct
  type elt = X.t

تحدّد الوسيطة X، من النوع Ordered، نوع العناصر. ويجب أن تكون هذه مزوَّدة بدالة مقارنة تقابل ترتيب الأولوية (انظر البرنامج 33 من الفصل 5 للحصول على التوقيعة Ordered). ومن ثمّ يكون النوع elt لعناصر الطابور مرادفًا لـ X.t. والنوع t هو نوع الأشجار الثنائية.

  type t = Empty | Node of t * elt * t

تعريفا الكومة الفارغة والدالة is_empty واضحان.

  let empty = Empty
  let is_empty h =
    h = Empty

تتيح بنية الكومة وصولًا فوريًا إلى أصغر عنصر.

  let get_min = function
    | Empty -> invalid_arg "get_min"
    | Node (_, x, _) -> x

يكمن كل التلطّف في هذه البنية في الدالة merge التي تدمج كومتين. وبافتراض أننا كتبنا هذه الدالة بالفعل، يصبح من السهل كتابة الدالتين add وremove_min. وفعلًا، تتمثل إضافة عنصر x إلى كومة h في دمج الكومة التي تحتوي على العنصر الوحيد x مع h.

  let add x h =
    merge (Node (Empty, x, Empty)) h

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

  let remove_min = function
    | Empty -> invalid_arg "remove_min"
    | Node (a, _, b) -> merge a b

لم يبق علينا الآن سوى كتابة الدالة merge التي تدمج كومتين ha وhb. وإذا كانت إحدى الكومتين فارغة، فطريقة ذلك واضحة.

  let rec merge ha hb = match ha, hb with
    | Empty, h | h, Empty ->
        h

أما إذا لم تكن أيا من الكومتين فارغة، فإننا نبني الكومة الناتجة كما يلي. جذرها هو الأصغر بين جذري ha وhb. ولنفترض أن جذر ha هو الأصغر.

    | Node (la, xa, ra), Node (lb, xb, rb) ->
        if X.compare xa xb <= 0 then

يجب علينا الآن تحديد الشجرتين الفرعيتين للعقدة Node(_,xa,_). وهناك عدة إمكانات تنتج عن استدعاء merge استدعاءً تكراريًا على اثنتين من الأشجار الثلاث la وra وhb، وعن اختيار النتيجة شجرةً فرعية يسرى أو يمنى. ومن بين هذه الإمكانات، نختار تلك التي تُجري دورانًا للشجرتين الفرعيتين من اليمين إلى اليسار، بما يضمن الموازنة الذاتية. وهكذا، تتخذ ra موضع la، وتُدمج la مع hb.

          Node (ra, xa, merge la hb)

أما الحالة الأخرى، التي يكون فيها جذر hb هو الأصغر، فهي متناظرة.

        else Node (rb, xb, merge lb ha)

الكود الكامل لطوابير الأولوية الدائمة معطى في البرنامج 66.

التعقيد

من الواضح أن للدوال empty وis_empty وget_min كلفة ثابتة. ويكون التحليل أكثر دقة في حالة الدالة merge، ومن ثمّ add وremove_min. وفي أسوأ الحالات، قد تكون كلفة merge بقدر العدد الإجمالي للعناصر. غير أنه، بالنسبة إلى متتالية من عمليات add وremove_min، تُنفَّذ على التوالي على كومة، لا يمكن أن تحدث أسوأ حالة كهذه في كل مرة. ويمكننا أن نبيّن أن الكلفة المطفأة (amortized) لكل عملية هي في الواقع O(log N)، حيث N هو عدد العناصر في الكومة. ولتحليل هذا التعقيد، نحيل القارئ إلى مقالة Sleator وTarjan التي قدّمت الأكوام ذاتية الموازنة [22] أو إلى الفصل الخاص بالأكوام بقلم Okasaki في متعة البرمجة (The Fun of Programming) [10].

    type ’a t = { mutable o : ’a list; mutable i : ’a list }

    val push_front : ’a -> ’a t -> ’a t
    val push_back : ’a -> ’a t -> ’a t
    val pop_front : ’a t -> ’a * ’a t
    val pop_back : ’a t -> ’a * ’a t

    type ’a t = { li : int; i : ’a list; lo : int; o : ’a list }

    type pointer
    val add: elt -> t -> pointer

    type pointer = { elt: elt; mutable index: int }

  val change_priority : pointer -> elt -> t -> unit

  module Make(P: Ordered)(V: WithDummy) :
  sig
    type t
    type priority = P.t
    type value = V.t
    val create : unit -> t
    val is_empty : t -> bool
    val add : priority -> value -> t -> unit
    val get_min : t -> priority * value
    val remove_min : t -> unit
  end