هیپ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مثالی از یک هیپ بیشینه ی دودویی

در علوم رایانه، هیپ یک ساختمان داده‌ی درخت (ساختار داده) است که شرط "اگر B بچه ی A بود، آنگاه مقدار گره‌ی A بزرگتر مساوی مقدار گره‌ی B باشد" را ارضا کند. این مسئله بیانگر این است که گره ی با بیشترین مقدار همواره در ریشه قرار می گیرد و بنابراین چنین هیپی، هیپ بیشینه نامیده می شود. بر روی این که هر گره چند گره فرزند داشته باشد، هیچ محدودیتی وجود ندارد، حال آنکه در عمل معمولاً هر گره، دو فرزند دارد. هیپ یک داده ساختار بهینه برای پیاده سازی یک داده ی انتزاعی به نام صف اولویت دار می باشد. هیپ ها در الگوریتم های زیادی مانند الگوریتم دیکسترا در نظریه گراف کاربرد دارند.

داده ساختار هیپ نباید با مفهوم هیپ که برای اختصاص پویای حافظه به کار می رود اشتباه شود. بعضی از زبان های برنامه نویسی مانند لیسپ برای این شیوه ی اختصاص حافظه از داده ساختار هیپ استفاده می کنند. هیپ ها معمولاً به صورت آرایه پیاده سازی می شوند و نیاز به اشاره گر ندارند.

توابعی که بر روی هیپ ها پیاده سازی می شوند عبارتند از:

  • create-heap: که یک هیپ خالی می سازد.
  • find-max و find-min: بیشترین عنصر هیپ بیشینه یا کمترین عنصر هیپ کمینه را بر می گرداند.
  • delete-max یا delete-min: ریشه ی هیپ را پاک میکند.
  • increase-key یا decrease-key: مقدار یک گره در هیپ را به روز میکند.
  • insert: یک گره ی جدید را به هیپ اضافه میکند.
  • merge: دو هیپ را ترکیب میکند و یک هیپ میسازد که عناصر هر دو را داشته باشد.

انواع هیپ[ویرایش]

مقایسه ی محدودیت‌های نظری انواع هیپ[ویرایش]

پیچیدگی زمانی تعدادی از انواع هیپ برای تابع های مختلف در جدول زیر آمده است. خانه های ستاره دار نشان دهنده ی زمان سرشکن است و خانه هایی که دو ستاره دارند نشاند دهنده ی این است که n اندازه ی هیپ بزرگتر است.

Operation Binary Binomial Fibonacci heap Pairing heap Brodal queue
create-heap Θ(1) Θ(1) Θ(1)  ? O(1)
findMin Θ(1) O(log n) Θ(1) O(1)* O(1)
deleteMin Θ(log n) Θ(log n) O(log n)* O(log n)* O(log n)
insert Θ(log n) O(log n) Θ(1) O(1)* O(1)
decreaseKey Θ(log n) Θ(log n) Θ(1)* O(log n)* O(1)
merge Θ(n) O(log n)** Θ(1) O(1)* O(1)

کاربردها[ویرایش]

داده ساختار هیپ کاربرد های زیادی دارد که برخی از آنها عبارتند از:

  • مرتب‌سازی هرمی: یکی از بهترین شیوه های مرتب سازی است.
  • الگوریتم انتخاب: برای یافتم عنصر بیشینه، کمینه، میانه و یا حتی kامین عنصر در زمان خطی به کار می رود.
  • الگوریتم های گراف: با استفاده از هیپ به عنوان زمان بهینه ی پیمایش، زمان اجرا به صورت چند جمله ای کاهش می یابد. این الگوریتم ها برای مواردی مانند الگوریتم پریم و الگوریتم دیکسترا استفاده می شوند.

پیاده‌سازی[ویرایش]

  • ++C: در کتابخانه ی این زبان برنامه نویسی تابع هایی مانند make_heap، push_heap و pop_heap برای هیپ ها پیاده سازی شده است. در این توابع، داده ها به صورت آرایه داده می شوند و از تبدیل array-to-heap استفاده می شود.
  • Java: در جاوا 2 برای پیاده سازی هیپ دوتایی از کلاس java.util.PriorityQueue<E> استفاده می شود.
  • پایتون: در این زبان از ماژول heapq استفاده می شود که یک هیپ دودویی را به کمک یک صف اولویت دار پیاده سازی می کند.
  • PHP: که دو تابع SplMaxHeap و SplMinHeap را برای پیاده سازی maxheap و minheap دارد.
  • Perl: از سیپن برای پیاده سازی هیپ های فیبوناتچی و دوتایی استفاده می کند.
  • Go: این زبان یک بسته ی هیپ دارد که در پیاده سازی از آن استفاده می کند.


منابع[ویرایش]

  1. [۱] Beap
  2. [۲] Leftist heap
  3. [۳] Skew heap


[[۴]]