هرم دی‌تایی

d -ary heap یا d-heap یک ساختمان داده صف اولویت دار است، یک کلیت از یک هیپ دودویی که گره‌ها به جای دو فرزند الگو:Math فرزند دارند. بنابراین هیپ دودویی یک هیپ ـ 2 است. طبق گفته‌های Tarjan و Jensen و همکارانشان ، هیپ الگو:Math تایی توسط Donald B. Hohnson در سال 1975 ابداع شده‌است.

این ساختمان داده به عملیات‌های با اولویت کمتر اجازه می دهد تا سریع تر از هیپ دودویی عمل کنند، با هزینه کندتر حذف کردن کمترین عملیات ها. این موازنه منجر به بهتر اجرا شدن الگوریتم‌هایی مثل الگوریتم دیکسترا که در آن کاهش عملیات‌های اولویت دار شایع تر از حذف حداقل عملیات‌ها است، شده‌است. علاوه بر این، هیپ الگو:Math تایی بهتر از هیپ دودویی از حافظه نهان استفاده می‌کنند، و در عمل به آن‌ها اجازه می‌دهد تا سریع تر اجرا شوند با اینکه در تئوری بدترین سرعت اجرای بیشتری دارند. همانند هیپ دودویی، هیپ‌های الگو:Math تایی الگوریتم درجا هستند که از هیچ فضای ذخیره‌سازی اضافه‌ای فراتر از آنچه که برای ذخیره اعضای آرایه در هیپ نیاز است، استفاده نمی‌کنند. همانند مبنای 2، هیپ الگو:Mathتایی هم یک ساختار اطلاعاتی درونی است که هیچ حافظه ی جانبی را فراتر از آنچه که نیاز دارد تا اعداد یک مبنا را ذخیره کند استفاده و اشغال نمی‌کند.

ساختمان داده

هیپ الگو:Mathتایی شامل آرایه الگو:Math عضوی است، که هر کدام از آن‌ها دارای اولویت در ارتباط با آن است. این اعضا ممکن است به عنوان گره‌هایی در یک درخت الگو:Mathتایی کامل که در جستجوی سطح اول ذکر شده، دیده شوند. عضوی که در جایگاه 0 آرایه قرار دارد، ریشه درخت را تشکیل می دهد، و اعضایی که در موقعیت $1-d$ آرایه قرار دارند، فرزندان ریشه و $d^2$ عضو بعدی، نوه‌های آن هستند، و... . بنابراین، پدر عضوی که در مکان الگو:Math است، (برای هر الگو:Math ) عضوی است که در مکان کف $((1-i)/d)$ الگو:چراست و فرزندان آن اعضایی هستند که در مکان id + 1 تا id + d قرار دارند. با توجه به ویژگی هیپ در مین هیپ هر عضو یک اولویت دارد که حداقل به بزرگی پدرش است؛ در ماکس هیپ، هر عضو دارای اولولیتی حداکثر برابر پدرش است.

عضو دارای اولویت کمتر در مین هیپ (یا عضو دارای بیشترین اولویت در ماکس هیپ) همیشه در مکان صفر آرایه قرار می‌گیرد. برای حذف این عضو از صف اولویت، آخرین عضو x آرایه جای آن را می‌گیرد، و سایز آرایه یکی کم می‌شود. سپس، در صورتی که عضو x و فرزندانش خاصیت‌های هیپ را برآورده نکنند، x با یکی از فرزندانش جابجا می‌شود. (در مین هیپ عضوی که دارای کمترین اولویت است، یا در ماکس هیپ عضو دارای بیشترین اولویت). آن را با اعضای پایین‌تر در درخت و عضوهای بعدی در آرایه جابجا می کنیم، تا جایی که سرانجام خاصیت‌های هیپ برآورده بشود. همانند فرایند جابجایی رو به پایین، برای افزایش اولویت هر عضو در مین هیپ یا کاهش اولویت هر عضو در ماکس هیپ استفاده می‌شود.

برای وارد کردن عضو جدید به هیپ، عضو به آخر آرایه اضافه می‌شود و سپس در صورتی‌که خاصیت‌های هیپ نقض شده باشد، آن عضو با پدرش جابجا می‌شود. آن را در درخت به بالا انتقال داده و در آرایه به عضوهای اولیه منتقل می کنیم، تا جایی که خاصیت‌های هیپ برآورده بشود. همانند فرایند جابجایی رو به بالا، برای کاهش اولویت هر عضو در مین هیپ یا افزایش اولویت هر عضو در ماکس هیپ استفاده می‌شود.

برای ایجاد یک هیپ جدید از آرایه الگو:Math عضوی، ممکن است یک حلقه در جهت معکوس ایجاد شود. این حلقه از عضوی با مکان ${\displaystyle }$ شروع شده و به عضو در مکان صفر ختم می‌شود. فرایند جابجایی رو به پایین برای هر عضو اجرا می‌شود.

تجزیه و تحلیل

در هیپ الگو:Math تایی با داشتن الگو:Math عضو، هر دو فرایند جابجایی رو به بالا و فرایند جابجایی رو به پایین به تعداد $1-n$ الگو:چر جابجایی وجود دارد. در فرایند جابجایی رو به بالا، هر تعویض شامل تنها یک مقایسه هر عضو با پدرش است و یک زمان ثابت طول می کشد. بنابراین، زمان وارد کردن یک عضو جدید در هیپ، کاهش اولویت یک عضو در مین هیپ، یا افزایش اولویت یک عضو در ماکس هیپ $dgol/ngol=n_{d}gol$ می‌باشد. در فرایند جابجایی رو به پایین، هر تعویض شامل الگو:Math مقایسه است و الگو:Math زمان لازم دارد. 1 – الگو:Math مقایسه لازم است تا کوچکترین و بزرگترین فرزند تعیین شود و سپس یک مقایسه دیگر با پدر تا تعیین شود که آیا تعویض نیاز است یا نه. بنابراین، زمان حذف کردن عضو ریشه، افزایش اولویت هر عضو در مین هیپ، یا کاهش اولویت هر عضو در ماکس هیپ، $(dgol/ngol)O$ می‌باشد.

وقتی یک هیپ الگو:Math تایی از n عضو ساخته می‌شود، بیشتر اعضا در مکانی قرار دارند که سرانجام برگ‌های درخت الگو:Math تایی را تشکیل می دهند و جابجایی رو به پایین برای آن‌ها صورت نمی‌گیرد. در حداکثر $(dgol/ngold)O$ الگو:چر از اعضا، که برگ نیستند حداقل یک بار جابجایی رو به پایین با هزینه زمانی الگو:Math برای یافتن فرزند برای جابجایی با آن صورت می‌گیرد. در حداکثر $1+d/n$ الگو:چر گره ممکن است جابجایی رو به پایین دو بار صورت بگیرد، که در این صورت الگو:Math هزینه اضافی برای دومین جابجایی، فراتر از هزینه‌ای که برای دوره اول محاسبه شده بود، نیاز است و... بنابراین، مقدار کل زمانی که برای ساختن یک هیپ با این روش نیاز است برابر است با: الگو:چپ‌چین

 $1{+}^{2}d/n$  

فضای استفاده شده توسط هیپ الگو:Math تایی با عملیات‌های درج و حذف کوچکترین عضو خطی است، به‌طوری‌که نسبت به آرایه‌های دیگری که شامل لیستی از اعضا در هیپ هستند، از فضای ذخیره‌سازی اضافی استفاده نمی‌کند. اگر تغییراتی در اولویت‌های اعضای موجود نیاز باشد، یکی از اعضا باید اشاره گرهایی که فقط فضای ذخیره‌سازی خطی دوباره از آن‌ها استفاده می‌کند را از اعضا به مکانشان در هیپ نگه دارد.

کاربردها

الگوریتم دیکسترا برای یافتن کوتاهترین مسیر در گراف‌ها و الگوریتم پریم برای درخت فراگیر مینیمم، هر دو از مین هیپ استفاده می‌کنند که در آن الگو:Math عملیات حذف مینیمم و الگو:Math عملیات کاهش اولویت وجود دارد. که الگو:Math تعداد رئوس در گراف و m تعداد یال‌ها است. با استفاده از یک هیپ الگو:Math تایی با $\sum _{i=1}^{{\log }_{d}n}(\frac{n}{d^i}+1)O(d)=O(n).$ الگو:چر کل زمان برای این دو نوع عملیات ممکن است متعادل شود که کل زمان برای الگوریتم برابر می‌شود با $n/m=d$ الگو:چر. زمان اجرای بهبود یافته هیپ دودویی این الگوریتم‌ها وقتی که تعداد یال‌ها به‌طور قابل ملاحظه‌ای بیشتر از تعداد رأس‌ها باشد، برابر است با $(n_{n/m}golm)O$ . یک ساختمان داده صف اولویت دیگر، هیپ فیبوناتچی است که زمان اجرای نظری بهتر $(ngolm)O$ را می‌دهد. ولی در عمل، به‌طور کلی هیپ الگو:Mathتایی‌ها حداقل به همان اندازه سریع یا اغلب سریع تر از هیپ فیبونانچی برای این کاربرد هستند.

4-هیپ‌ها در عمل ممکن است عملکرد بهتری حتی در عملیات‌های حذف مینیمم نسبت به هیپ دودویی داشته باشند. علاوه بر این، معمولاً هیپ‌های الگو:Mathتایی بسیار سریع تر از هیپ دودویی اجرا می‌شود. به خاطر اندازه هیپ که بیشتر از اندازه حافظه نهان کامپیوتر است. هیپ دودویی معمولاً به کش سی‌پی‌یو بیشتر و page fault حافظه مجازی بیشتری نسبت به هیپ الگو:Mathتایی نیاز دارد. الگو:ساختمان داده‌ها

منابع

الگو:پانویس http://en.wikipedia.org/wiki/D-ary_heap

پیوند به بیرون

• C++ implementation of generalized heap with D-Heap support