ادغام K لیست پیوندی مرتب شده با استفاده از صف اولویت دار

اشتراک گذاری

به ما تعداد K لیست پیوندی داده شده که هر کدام جداگانه مرتب هستند. ما می خواهیم از این لیست های مرتب، یک لیست مرتب واحد بسازیم و همه آن ها را ادغام کنیم.

مثال:

به طور مثال داریم:

شیوه ما در این مطلب آموزشی از وبسایت اوپن مایند، ادغام لیست های جداگانه به وسیله صف اولویت دار است.

الگوریتم ادغام:

الگوریتم کار به طریق زیر بیان می شود:

  1. یک صف اولویت دار ایجاد می کنیم.
  2. گره اول همه K لیست پیوندی را به صف اولویت دار اضافه می کنیم.
  3. تا زمانی که صف اولویت دار خالی نشده است کار های زیر را انجام می دهیم:
    1. یک گره را از صف اولویت دار خارج می کنیم (گره با کمترین مقدار خارج می شود).
    2. اگر این گره خارج شده یک گره بعدی دارد، بعدی آن را به صف اولویت دار وارد می کنیم.
    3. گره خارج شده از صف را به انتهای لیست پیوندی نهایی (ادغام شده) اضافه می کنیم.
  4. لیست نهایی (ادغام شده) را بر می گردانیم.

 

توجه:

در کد جاوای زیر، تابع مقایسه گر کلاس صف اولویت دار را بازنویسی کرده ایم تا بتواند بر اساس ساختار گره که توسط خودمان تعریف شده، مقایسه بین گره ها را انجام دهد و اولویت را به گره ای با کمترین مقدار بدهد.

 

کد جاوای ادغام K لیست پیوندی مرتب با صف اولویت دار:

 

خروجی اجرای کد بالا به شکل زیر است:

 

 

نظرتان را برای ما بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *