هرم دیتایی
d -ary heap یا d-heap یک ساختمان داده صف اولویت دار است، یک کلیت از یک هیپ دودویی که گرهها به جای دو فرزند d فرزند دارند. بنابراین هیپ دودویی یک هیپ ـ 2 است. طبق گفتههای Tarjan و Jensen و همکارانشان ، هیپ d تایی توسط Donald B. Hohnson در سال 1975 ابداع شدهاست.
این ساختمان داده به عملیاتهای با اولویت کمتر اجازه می دهد تا سریع تر از هیپ دودویی عمل کنند، با هزینه کندتر حذف کردن کمترین عملیات ها. این موازنه منجر به بهتر اجرا شدن الگوریتمهایی مثل الگوریتم دیکسترا که در آن کاهش عملیاتهای اولویت دار شایع تر از حذف حداقل عملیاتها است، شدهاست. علاوه بر این، هیپ d تایی بهتر از هیپ دودویی از حافظه نهان استفاده میکنند، و در عمل به آنها اجازه میدهد تا سریع تر اجرا شوند با اینکه در تئوری بدترین سرعت اجرای بیشتری دارند. همانند هیپ دودویی، هیپهای d تایی الگوریتم درجا هستند که از هیچ فضای ذخیرهسازی اضافهای فراتر از آنچه که برای ذخیره اعضای آرایه در هیپ نیاز است، استفاده نمیکنند. همانند مبنای 2، هیپ dتایی هم یک ساختار اطلاعاتی درونی است که هیچ حافظه ی جانبی را فراتر از آنچه که نیاز دارد تا اعداد یک مبنا را ذخیره کند استفاده و اشغال نمیکند.
ساختمان داده
هیپ dتایی شامل آرایه n عضوی است، که هر کدام از آنها دارای اولویت در ارتباط با آن است. این اعضا ممکن است به عنوان گرههایی در یک درخت dتایی کامل که در جستجوی سطح اول ذکر شده، دیده شوند. عضوی که در جایگاه 0 آرایه قرار دارد، ریشه درخت را تشکیل می دهد، و اعضایی که در موقعیت
عضو دارای اولویت کمتر در مین هیپ (یا عضو دارای بیشترین اولویت در ماکس هیپ) همیشه در مکان صفر آرایه قرار میگیرد. برای حذف این عضو از صف اولویت، آخرین عضو x آرایه جای آن را میگیرد، و سایز آرایه یکی کم میشود. سپس، در صورتی که عضو x و فرزندانش خاصیتهای هیپ را برآورده نکنند، x با یکی از فرزندانش جابجا میشود. (در مین هیپ عضوی که دارای کمترین اولویت است، یا در ماکس هیپ عضو دارای بیشترین اولویت). آن را با اعضای پایینتر در درخت و عضوهای بعدی در آرایه جابجا می کنیم، تا جایی که سرانجام خاصیتهای هیپ برآورده بشود. همانند فرایند جابجایی رو به پایین، برای افزایش اولویت هر عضو در مین هیپ یا کاهش اولویت هر عضو در ماکس هیپ استفاده میشود.
برای وارد کردن عضو جدید به هیپ، عضو به آخر آرایه اضافه میشود و سپس در صورتیکه خاصیتهای هیپ نقض شده باشد، آن عضو با پدرش جابجا میشود. آن را در درخت به بالا انتقال داده و در آرایه به عضوهای اولیه منتقل می کنیم، تا جایی که خاصیتهای هیپ برآورده بشود. همانند فرایند جابجایی رو به بالا، برای کاهش اولویت هر عضو در مین هیپ یا افزایش اولویت هر عضو در ماکس هیپ استفاده میشود.
برای ایجاد یک هیپ جدید از آرایه n عضوی، ممکن است یک حلقه در جهت معکوس ایجاد شود. این حلقه از عضوی با مکان
تجزیه و تحلیل
در هیپ d تایی با داشتن n عضو، هر دو فرایند جابجایی رو به بالا و فرایند جابجایی رو به پایین به تعداد
وقتی یک هیپ d تایی از n عضو ساخته میشود، بیشتر اعضا در مکانی قرار دارند که سرانجام برگهای درخت d تایی را تشکیل می دهند و جابجایی رو به پایین برای آنها صورت نمیگیرد. در حداکثر
فضای استفاده شده توسط هیپ d تایی با عملیاتهای درج و حذف کوچکترین عضو خطی است، بهطوریکه نسبت به آرایههای دیگری که شامل لیستی از اعضا در هیپ هستند، از فضای ذخیرهسازی اضافی استفاده نمیکند. اگر تغییراتی در اولویتهای اعضای موجود نیاز باشد، یکی از اعضا باید اشاره گرهایی که فقط فضای ذخیرهسازی خطی دوباره از آنها استفاده میکند را از اعضا به مکانشان در هیپ نگه دارد.
کاربردها
الگوریتم دیکسترا برای یافتن کوتاهترین مسیر در گرافها و الگوریتم پریم برای درخت فراگیر مینیمم، هر دو از مین هیپ استفاده میکنند که در آن n عملیات حذف مینیمم و m عملیات کاهش اولویت وجود دارد. که n تعداد رئوس در گراف و m تعداد یالها است. با استفاده از یک هیپ d تایی با
4-هیپها در عمل ممکن است عملکرد بهتری حتی در عملیاتهای حذف مینیمم نسبت به هیپ دودویی داشته باشند. علاوه بر این، معمولاً هیپهای dتایی بسیار سریع تر از هیپ دودویی اجرا میشود. به خاطر اندازه هیپ که بیشتر از اندازه حافظه نهان کامپیوتر است. هیپ دودویی معمولاً به کش سیپییو بیشتر و page fault حافظه مجازی بیشتری نسبت به هیپ dتایی نیاز دارد.
منابع
- ↑ Tarjan, R. E. (1983), "3.2. d-heaps", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 34–38.
- ↑ Weiss, M. A. (2007), "d-heaps", Data Structures and Algorithm Analysis (2nd ed.), Addison-Wesley, p. 216, ISBN 0321370139.
- ↑ Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF), archived from the original (PDF) on 9 June 2007, retrieved 25 February 2012.
- ↑ Johnson, D. B. (1975), "Priority queues with update and finding minimum spanning trees", Information Processing Letters, 4 (3): 53–57, doi:10.1016/0020-0190(75)90001-0.
- ↑ (Tarjan 1983), pp. 77 and 91.
- ↑ Mortensen, C. W.; Pettie, S. (2005), "The complexity of implicit and space efficient priority queues", Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3608, Springer-Verlag, pp. 49–60, doi:10.1007/11534273_6, ISBN 978-3-540-28101-6.
- ↑ Cherkassky, B. V.; Goldberg, A. V.; Radzik, T. (1996), "Shortest paths algorithms: Theory and experimental evaluation", Mathematical Programming, 73 (2): 129–174, doi:10.1007/BF02592101.
- ↑ Naor, D.; Martel, C. U.; Matloff, N. S. (1991), "Performance of priority queue structures in a virtual memory environment", Computer Journal, 34 (5): 428–437, doi:10.1093/comjnl/34.5.428.
- ↑ Kamp, Poul-Henning (2010), "You're doing it wrong", ACM Queue, 8 (6).