هرم (علوم رایانه)

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

در علوم رایانه، هرم یا هیپ (heap) یک ساختمان داده‌ی درخت (ساختار داده) است که شرط «اگر 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 Θ(۱) Θ(۱) Θ(۱)  ? O(1)
findMin Θ(۱) O(log n) Θ(۱) O(1)* O(1)
deleteMin Θ(log n) Θ(log n) O(log n)* O(log n)* O(log n)
insert Θ(log n) O(log n) Θ(۱) O(1)* O(1)
decreaseKey Θ(log n) Θ(log n) Θ(۱)* O(log n)* O(1)
merge Θ(n) O(log n)** Θ(۱) O(1)* O(1)

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

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

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

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

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

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

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


[[۴]]