هرم دی‌تایی: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۲۵ فوریهٔ ۲۰۱۲، ساعت ۱۲:۴۵

d -ary heap یا d-heap یک ساختمان داده صف اولویت دار است، یک کلیت از یک هیپ دودویی که گره ها به جای دو فرزند $d$ فرزند دارند.^[۱]^[۲] بنابراین هیپ دودویی یک هیپ ـ 2 است. طبق گفته های Tarjan و Jensen و همکارانشان ^[۳] ، هیپ $d$ تایی توسط Donald B. Hohnson در سال 1975 ابداع شده است.^[۴]

این ساختمان داده به عملیات های با اولویت کمتر اجازه می دهد تا سریع تر از هیپ دودویی عمل کنند، با هزینه کندتر حذف کردن کمترین عملیات ها. این موازنه منجر به بهتر اجرا شدن الگوریتم هایی مثل الگوریتم دیکسترا که در آن کاهش عملیات های اولویت دار شایع تر از حذف حداقل عملیات ها است، شده است.^[۴]^[۵] علاوه بر این، هیپ $d$ تایی بهتر از هیپ دودویی از حافظه نهان استفاده می کنند، و در عمل به آنها اجازه میدهد تا سریع تر اجرا شوند با اینکه در تئوری بدترین سرعت اجرای بیشتری دارند. همانند هیپ دودویی، هیپ های $d$ تایی الگوریتم درجا هستند که از هیچ فضای ذخیره سازی اضافه ای فراتر از آنچه که برای ذخیره اعضای آرایه در هیپ نیاز است، استفاده نمی کنند. همانند مبنای 2، هیپ $d$ تایی هم یک ساختار اطلاعاتی درونی است که هیچ حافظه ی جانبی را فراتر از آنچه که نیاز دارد تا اعداد یک مبنا را ذخیره کند استفاده و اشغال نمی کند. ^[۱]^[۶]

ساختمان داده

هیپ $d$ تایی شامل آرایه $n$ عضوی است، که هر کدام از آنها دارای اولویت در ارتباط با آن است. این اعضا ممکن است به عنوان گره هایی در یک درخت $d$ تایی کامل که در جستجوی سطح اول ذکر شده، دیده شوند. عضوی که در جایگاه 0 آرایه قرار دارد، ریشه درخت را تشکیل می دهد، و اعضایی که در موقعیت 1– $d$ آرایه قرار دارند، فرزندان ریشه و $^{2}d$ عضو بعدی، نوه های آن هستند، و... . بنابراین، پدر عضوی که در مکان $i$ است، (برای هر $i > 0$ ) عضوی است که در مکان کف ${(d/(1-i))}$ ‎است و فرزندان آن اعضایی هستند که در مکان $1 + id$ تا $d + id$ قرار دارند. با توجه به ویژگی هیپ در مین هیپ هر عضو یک اولویت دارد که حداقل به بزرگی پدرش است؛ در ماکس هیپ، هر عضو دارای اولولیتی حداکثر برابر پدرش است.^[۱]^[۲]

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

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

برای ایجاد یک هیپ جدید از آرایه $n$ عضوی، ممکن است یک حلقه در جهت معکوس ایجاد شود. این حلقه از عضوی با مکان ${1-n}$ شروع شده و به عضو در مکان صفر ختم می شود. فرایند جابجایی رو به پایین برای هر عضو اجرا می شود.^[۱]^[۲]

تجزیه و تحلیل

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

وقتی یک هیپ $d$ تایی از n عضو ساخته می شود، بیشتر اعضا در مکانی قرار دارند که سرانجام برگ های درخت $d$ تایی را تشکیل می دهند و جابجایی رو به پایین برای آنها صورت نمی گیرد. در حداکثر ${1+d/n}$ ‎ از اعضا، که برگ نیستند حداقل یک بار جابجایی رو به پایین با هزینه زمانی $(d)O$ برای یافتن فرزند برای جابجایی با آن صورت می گیرد. در حداکثر ${1+^{2}d/n}$ ‎ گره ممکن است جابجایی رو به پایین دو بار صورت بگیرد، که در این صورت $(d)O$ هزینه اضافی برای دومین جابجایی، فراتر از هزینه ای که برای دوره اول محاسبه شده بود، نیاز است و... بنابراین، مقدار کل زمانی که برای ساختن یک هیپ با این روش نیاز است برابر است با:

  $\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).$   ^[۱]^[۲]

فضای استفاده شده توسط هیپ $d$ تایی با عملیات های درج و حذف کوچکترین عضو خطی است، به طوری که نسبت به آرایه های دیگری که شامل لیستی از اعضا در هیپ هستند، از فضای ذخیره سازی اضافی استفاده نمی کند.^[۱]^[۶] اگر تغییراتی در اولویت های اعضای موجود نیاز باشد، یکی از اعضا باید اشاره گرهایی که فقط فضای ذخیره سازی خطی دوباره از آنها استفاده میکند را از اعضا به مکانشان در هیپ نگه دارد.^[۱]

کاربردها

الگوریتم دیکسترا برای یافتن کوتاهترین مسیر در گراف ها و الگوریتم پریم برای درخت فراگیر مینیمم، هر دو از مین هیپ استفاده می کنند که در آن $n$ عملیات حذف مینیمم و $m$ عملیات کاهش اولویت وجود دارد. که $n$ تعداد رئوس در گراف و m تعداد یال ها است. با استفاده از یک هیپ $d$ تایی با ${n/m=d}$ ‎ کل زمان برای این دو نوع عملیات ممکن است متعادل شود که کل زمان برای الگوریتم برابر می شود با ${(n_{n/m}golm)O}$ ‎. زمان اجرای بهبود یافته هیپ دودویی این الگوریتم ها وقتی که تعداد یال ها به طور قابل ملاحظه ای بیشتر از تعداد راس ها باشد، برابر است با ${(ngolm)O}$ .^[۴]^[۵] یک ساختمان داده صف اولویت دیگر، هیپ فیبوناتچی است که زمان اجرای نظری بهتر ${(ngoln+m)O}$ را می دهد. ولی در عمل، به طور کلی هیپ $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).
↑ ^۴٫۰ ^۴٫۱ ^۴٫۲ 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).

http://en.wikipedia.org/wiki/D-ary_heap

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

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

[t83-1] ۱٫۰۰ ^۱٫۰۱ ^۱٫۰۲ ^۱٫۰۳ ^۱٫۰۴ ^۱٫۰۵ ^۱٫۰۶ ^۱٫۰۷ ^۱٫۰۸ ^۱٫۰۹ ^۱٫۱۰ 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.

[w07-2] ۲٫۰ ^۲٫۱ ^۲٫۲ ^۲٫۳ ^۲٫۴ ^۲٫۵ ^۲٫۶ ^۲٫۷ Weiss, M. A. (2007), "d-heaps", Data Structures and Algorithm Analysis (2nd ed.), Addison-Wesley, p. 216, ISBN 0321370139.

[3] Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF).

[j75-4] ۴٫۰ ^۴٫۱ ^۴٫۲ 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.

[t2-5] ۵٫۰ ^۵٫۱ (Tarjan 1983), pp. 77 and 91.

[mp05-6] ۶٫۰ ^۶٫۱ 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.

[7] 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.

[nmm91-8] 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.

[k10-9] Kamp, Poul-Henning (2010), "You're doing it wrong", ACM Queue, 8 (6).

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

@@ خط ۱: / خط ۱: @@
-'''d -ary heap ''' یا ''' d-heap''' یک [[ساختمان داده]] [[صف اولویت دار]] است، یک کلیت از یک هیپ دودویی که گره ها به جای دو فرزند {{math|''d''}} فرزند دارند. بنابراین هیپ دودویی یک هیپ ـ 2 است. طبق گفته های Tarjan و Jensen و همکارانشان، هیپ {{math|''d''}} تایی توسط Donald B. Hohnson در سال 1975 ابداع شده است.
+'''d -ary heap ''' یا ''' d-heap''' یک [[ساختمان داده]] [[صف اولویت دار]] است، یک کلیت از یک هیپ دودویی که گره ها به جای دو فرزند {{math|''d''}} فرزند دارند.<ref name="t83"/><ref name="w07"/> بنابراین هیپ دودویی یک هیپ ـ 2 است. طبق گفته های Tarjan و Jensen و همکارانشان <ref>{{citation
+ | last1 = Jensen | first1 = C.
+ | last2 = Katajainen | first2 = J.
-این ساختمان داده به عملیات های با اولویت کمتر اجازه می دهد تا سریع تر از هیپ دودویی عمل کنند، با هزینه کندتر حذف کردن کمترین عملیات ها. این موازنه منجر به بهتر اجرا شدن الگوریتم هایی مثل [[الگوریتم دیکسترا]] که در آن کاهش عملیات های اولویت دار شایع تر از حذف حداقل عملیات ها است، شده است. علاوه بر این،  هیپ {{math|''d''}} تایی بهتر از هیپ دودویی از [[حافظه نهان]] استفاده می کنند، و در عمل به آنها اجازه می دهد تا سریع تر اجرا شوند با اینکه در تئوری بدترین سرعت اجرای بیشتری دارند.
+ | last3 = Vitale | first3 = F.
+ | title = An extended truth about heaps
+ | url = http://www.cphstl.dk/Report/In-place-multiway-heaps/experimental-study.pdf
+ | year = 2004}}.</ref> ، هیپ {{math|''d''}} تایی توسط Donald B. Hohnson در سال 1975 ابداع شده است.<ref name="j75">{{citation
+ | last = Johnson | first = D. B. | authorlink = Donald B. Johnson
+ | doi = 10.1016/0020-0190(75)90001-0
+ | journal = Information Processing Letters
+ | pages = 53–57
+ | title = Priority queues with update and finding minimum spanning trees
+ | volume = 4
+ | year = 1975
+ | issue = 3}}.</ref>
+این ساختمان داده به عملیات های با اولویت کمتر اجازه می دهد تا سریع تر از هیپ دودویی عمل کنند، با هزینه کندتر حذف کردن کمترین عملیات ها. این موازنه منجر به بهتر اجرا شدن الگوریتم هایی مثل [[الگوریتم دیکسترا]] که در آن کاهش عملیات های اولویت دار شایع تر از حذف حداقل عملیات ها است، شده است.<ref name="j75"/><ref name="t2"/> علاوه بر این،  هیپ {{math|''d''}} تایی بهتر از هیپ دودویی از [[حافظه نهان]] استفاده می کنند، و در عمل به آنها اجازه میدهد تا سریع تر اجرا شوند با اینکه در تئوری بدترین سرعت اجرای بیشتری دارند.
 همانند هیپ دودویی، هیپ های {{math|''d''}} تایی  [[الگوریتم درجا]] هستند که از هیچ فضای ذخیره سازی اضافه ای فراتر از آنچه که برای ذخیره اعضای آرایه در هیپ نیاز است، استفاده نمی کنند.
-همانند مبنای 2، هیپ {{math|''d''}}تایی هم یک ساختار اطلاعاتی درونی است که هیچ حافظه ی جانبی را فراتر از آنچه که نیاز دارد تا اعداد یک مبنا را ذخیره کند استفاده و اشغال نمی کند.
+همانند مبنای 2، هیپ {{math|''d''}}تایی هم یک ساختار اطلاعاتی درونی است که هیچ حافظه ی جانبی را فراتر از آنچه که نیاز دارد تا اعداد یک مبنا را ذخیره کند استفاده و اشغال نمی کند. <ref name="t83"/><ref name="mp05">{{citation
+ | last1 = Mortensen | first1 = C. W.
+ | last2 = Pettie | first2 = S.
+ | contribution = The complexity of implicit and space efficient priority queues
+ | doi = 10.1007/11534273_6
+ | pages = 49–60
+ | publisher = Springer-Verlag
+ | series = Lecture Notes in Computer Science
+ | title = [[SWAT and WADS conferences|Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings]]
+ | volume = 3608
+ | year = 2005
+ | isbn = 978-3-540-28101-6}}.</ref>
 == ساختمان داده ==
-هیپ {{math|''d''}}تایی شامل [[آرایه (رایانه) | آرایه]] {{math|''n''}} عضوی است، که هر کدام از آنها دارای اولویت در ارتباط با آن است. این اعضا ممکن است به عنوان گره هایی در یک درخت {{math|''d''}}تایی کامل که در [[جستجوی اول سطح]] ذکر شده، دیده شوند. عضوی که در جایگاه 0 آرایه قرار دارد، ریشه درخت را تشکیل می دهد، و اعضایی که در موقعیت 1–{{math|''d''}} آرایه قرار دارند، فرزندان ریشه و <math>d ^2</math> عضو بعدی، نوه های آن هستند، و... . بنابراین، پدر عضوی که در مکان {{math|''i''}} است، (برای هر {{math|''i'' > 0}} ) عضوی است که در مکان کف {{math|((''i'' &minus; 1)/''d'')}} است و فرزندان آن اعضایی هستند که در مکان {{math|''di'' + 1}} تا{{math|''di'' + ''d''}} قرار دارند. با توجه به ویژگی هیپ در مین هیپ هر عضو یک اولویت دارد که حداقل به بزرگی پدرش است؛ در ماکس هیپ، هر عضو دارای اولولیتی حداکثر برابر پدرش است.<ref name="t83">{{citation
+هیپ {{math|''d''}}تایی شامل [[آرایه (رایانه) | آرایه]] {{math|''n''}} عضوی است، که هر کدام از آنها دارای اولویت در ارتباط با آن است. این اعضا ممکن است به عنوان گره هایی در یک درخت {{math|''d''}}تایی کامل که در [[الگوریتم جستجوی اول سطح | جستجوی سطح اول]] ذکر شده، دیده شوند. عضوی که در جایگاه 0 آرایه قرار دارد، ریشه درخت را تشکیل می دهد، و اعضایی که در موقعیت 1–{{math|''d''}} آرایه قرار دارند، فرزندان ریشه و <math> ^ 2 d </math> عضو بعدی، نوه های آن هستند، و... . بنابراین، پدر عضوی که در مکان {{math|''i''}} است، (برای هر {{math|''i'' > 0}} ) عضوی است که در مکان کف
+<math>{(d /(1-i))}</math> {{چر}}است و فرزندان آن اعضایی هستند که در مکان {{math| 1 + ''id'' }} تا {{math| ''d'' + ''id'' }} قرار دارند. با توجه به ویژگی هیپ در مین هیپ هر عضو یک اولویت دارد که حداقل به بزرگی پدرش است؛ در ماکس هیپ، هر عضو دارای اولولیتی حداکثر برابر پدرش است.<ref name="t83">{{citation
  | last = Tarjan | first = R. E. | author-link = Robert Tarjan
  | contribution = 3.2. ''d''-heaps
@@ خط ۱۵: / خط ۴۳: @@
  | volume = 44
  | year = 1983}}.</ref><ref name="w07"/>
 عضو دارای اولویت کمتر در مین هیپ (یا عضو دارای بیشترین اولویت در ماکس هیپ) همیشه در مکان صفر آرایه قرار می گیرد. برای حذف این عضو از صف اولویت، آخرین عضو ''x'' آرایه جای آن را می گیرد، و سایز آرایه یکی کم می شود. سپس، در صورتی که عضو ''x'' و فرزندانش خاصیت های هیپ را برآورده نکنند، ''x'' با یکی از فرزندانش جابجا می شود. (در مین هیپ عضوی که دارای کمترین اولویت است، یا در ماکس هیپ عضو دارای بیشترین اولویت). آن را با اعضای پایین تر در درخت و عضوهای بعدی در آرایه جابجا می کنیم، تا جایی که سرانجام خاصیت های هیپ برآورده بشود. همانند فرایند جابجایی رو به پایین، برای افزایش اولویت هر عضو در مین هیپ یا کاهش اولویت هر عضو در ماکس هیپ استفاده می شود.<ref name="t83"/><ref name="w07"/>
 برای وارد کردن عضو جدید به هیپ، عضو به آخر آرایه اضافه می شود و سپس در صورتیکه خاصیت های هیپ نقض شده باشد، آن عضو با پدرش جابجا می شود. آن را در درخت به بالا انتقال داده و در آرایه به عضوهای اولیه منتقل می کنیم، تا جایی که خاصیت های هیپ برآورده بشود. همانند فرایند جابجایی رو به بالا، برای کاهش اولویت هر عضو در مین هیپ یا افزایش اولویت هر عضو در ماکس هیپ استفاده می شود.<ref name="t83"/><ref name="w07"/>
-برای ایجاد یک هیپ جدید از آرایه {{math|''n''}} عضوی، ممکن است یک حلقه در جهت معکوس ایجاد شود. این حلقه از عضوی با مکان {{math|''n'' &minus; 1}} شروع شده و به عضو در مکان صفر ختم می شود. فرایند جابجایی رو به پایین برای هر عضو اجرا می شود.<ref name="t83"/><ref name="w07"/>
+برای ایجاد یک هیپ جدید از آرایه {{math|''n''}} عضوی، ممکن است یک حلقه در جهت معکوس ایجاد شود. این حلقه از عضوی با مکان <math>{1 - n}</math>  شروع شده و به عضو در مکان صفر ختم می شود. فرایند جابجایی رو به پایین برای هر عضو اجرا می شود.<ref name="t83"/><ref name="w07"/>
 == تجزیه و تحلیل ==
-در هیپ {{math|''d''}} تایی با داشتن {{math|''n''}} عضو، هر دو فرایند جابجایی رو به بالا و فرایند جابجایی رو به پایین به تعداد {{math|1=log<sub>''d''</sub> ''n'' = log ''n'' / log ''d''}} جابجایی وجود دارد. در فرایند جابجایی رو به بالا، هر تعویض شامل تنها یک مقایسه هر عضو با پدرش است و یک زمان ثابت طول می کشد. بنابراین، زمان وارد کردن یک عضو جدید در هیپ، کاهش اولویت یک عضو در مین هیپ، یا افزایش اولویت یک عضو در ماکس هیپ  {{math|O(log ''n'' / log ''d'')}} می باشد. در فرایند جابجایی رو به پایین، هر تعویض شامل {{math|''d''}} مقایسه است و {{math|O(''d'')}} زمان لازم دارد. {{math|''d'' &minus; 1}} مقایسه لازم است تا کوچکترین و بزرگترین فرزند تعیین شود و سپس یک مقایسه دیگر با پدر تا تعیین شود که آیا تعویض نیاز است یا نه. بنابراین، زمان حذف کردن عضو ریشه، افزایش اولویت هر عضو در مین هیپ، یا کاهش اولویت هر عضو در ماکس هیپ، {{math|O(''d'' log ''n'' / log ''d'')}} می باشد.<ref name="t83"/><ref name="w07"/>
+در هیپ {{math|''d''}} تایی با داشتن {{math|''n''}} عضو، هر دو فرایند جابجایی رو به بالا و فرایند جابجایی رو به پایین به تعداد
+<math>{ d gol / n gol = n _ {d} gol }</math> {{چر}} جابجایی وجود دارد. در فرایند جابجایی رو به بالا، هر تعویض شامل تنها یک مقایسه هر عضو با پدرش است و یک زمان ثابت طول می کشد. بنابراین، زمان وارد کردن یک عضو جدید در هیپ، کاهش اولویت یک عضو در مین هیپ، یا افزایش اولویت یک عضو در ماکس هیپ  <math>{ (d gol / n gol)O }</math>  می باشد. در فرایند جابجایی رو به پایین، هر تعویض شامل {{math|''d''}} مقایسه است و {{math|(''d'')O}} زمان لازم دارد. 1 – {{math|''d''}} مقایسه لازم است تا کوچکترین و بزرگترین فرزند تعیین شود و سپس یک مقایسه دیگر با پدر تا تعیین شود که آیا تعویض نیاز است یا نه. بنابراین، زمان حذف کردن عضو ریشه، افزایش اولویت هر عضو در مین هیپ، یا کاهش اولویت هر عضو در ماکس هیپ، <math>{ (d gol / n gol d)O }</math> می باشد.<ref name="t83"/><ref name="w07"/>
-وقتی یک هیپ {{math|''d''}} تایی از ''n'' عضو ساخته می شود، بیشتر اعضا در مکانی قرار دارند که سرانجام برگ های درخت {{math|''d''}} تایی را تشکیل می دهند و جابجایی رو به پایین برای آنها صورت نمی گیرد. در حداکثر {{math|''n''/''d'' + 1}} از اعضا، که برگ نیستند حداقل یک بار جابجایی رو به پایین با هزینه زمانی {{math|O(''d'')}} برای یافتن فرزند برای جابجایی با آن صورت می گیرد. در حداکثر {{math|''n''/''d''<sup>2</sup> + 1}} گره ممکن است جابجایی رو به پایین دو بار صورت بگیرد، که در این صورت {{math|O(''d'')}} هزینه اضافی برای دومین جابجایی، فراتر از هزینه ای که برای دوره اول محاسبه شده بود، نیاز است و...
+وقتی یک هیپ {{math|''d''}} تایی از ''n'' عضو ساخته می شود، بیشتر اعضا در مکانی قرار دارند که سرانجام برگ های درخت {{math|''d''}} تایی را تشکیل می دهند و جابجایی رو به پایین برای آنها صورت نمی گیرد. در حداکثر <math>{1+d/n}</math> {{چر}} از اعضا، که برگ نیستند حداقل یک بار جابجایی رو به پایین با هزینه زمانی {{math|(''d'')O}} برای یافتن فرزند برای جابجایی با آن صورت می گیرد. در حداکثر <math>{1+ ^2d/n}</math> {{چر}} گره ممکن است جابجایی رو به پایین دو بار صورت بگیرد، که در این صورت {{math|(''d'')O}} هزینه اضافی برای دومین جابجایی، فراتر از هزینه ای که برای دوره اول محاسبه شده بود، نیاز است و...
 بنابراین، مقدار کل زمانی که برای ساختن یک هیپ با این روش نیاز است برابر است با:
+{{چپ‌چین}}
+  <math>\sum_{i=1}^{\log_d n} \left(\frac{n}{d^i}+1\right) O(d) = O(n).</math>  <ref name="t83"/><ref name="w07"/>
+{{پایان چپ‌چین}}
+فضای استفاده شده توسط  هیپ {{math|''d''}} تایی با عملیات های درج و حذف کوچکترین عضو خطی است، به طوری که نسبت به آرایه های دیگری که شامل لیستی از اعضا در هیپ هستند، از فضای ذخیره سازی اضافی استفاده نمی کند.<ref name="t83"/><ref name="mp05"/> اگر تغییراتی در اولویت های اعضای موجود نیاز باشد، یکی از اعضا باید اشاره گرهایی که فقط فضای ذخیره سازی خطی دوباره از آنها استفاده میکند را از اعضا به مکانشان در هیپ نگه دارد.<ref name="t83"/>
- :<math>\sum_{i=1}^{\log_d n} \left(\frac{n}{d^i}+1\right) O(d) = O(n).</math><ref name="t83"/><ref name="w07"/>
-فضای استفاده شده توسط {{math|''d''}} تایی با عملیات های درج و حذف کوچکترین عضو خطی است، به طوری که نسبت به آرایه های دیگری که شامل لیستی از اعضا در هیپ هستند، از فضای ذخیره سازی اضافی استفاده نمی کند.<ref name="t83"/>اگر تغییراتی در اولویت های اعضای موجود نیاز باشد، پس یکی از اعضا باید اشاره گرهایی که فقط فضای ذخیره سازی خطی دوباره از آنها استفاده میکند را از اعضا به مکانشان در هیپ نگه دارد.<ref name="t83"/>
 == کاربردها ==
-[[الگوریتم دیکسترا]] برای [[یافتن کوتاهترین مسیر]] در گراف ها و [[الگوریتم پریم]] برای [[درخت فراگیر مینیمم]]، هر دو از مین هیپ استفاده می کنند که در آن {{math|''n''}} عملیات حذف مینیمم و {{math|''m''}} عملیات کاهش اولویت وجود دارد. که {{math|''n''}} تعداد رئوس در گراف و ''m'' تعداد یال ها است. با استفاده از یک هیپ {{math|''d''}} تایی با {{math|1=''d'' = ''m''/''n''}} کل زمان برای این دو نوع عملیات ممکن است متعادل شود که کل زمان برای الگوریتم برابر می شود با{{math|O(''m'' log<sub>''m''/''n''</sub> ''n'')}}. زمان اجرای بهبود یافته هیپ دودویی این الگوریتم ها وقتی که تعداد یال ها به طور قابل ملاحظه ای بیشتر از تعداد راس ها باشد، برابر است با {{math|O(''m'' log ''n'')}}.<ref name="t2">{{harvtxt|Tarjan|1983}}, pp. 77 and 91.</ref>  یک ساختمان داده صف اولویت دیگر، [[هیپ فیبوناتچی]] است که زمان اجرای نظری بهتر {{math|O(''m'' + ''n'' log ''n'')}} را می دهد. ولی در عمل، به طور کلی هیپ {{math|''d''}}تایی ها حداقل به همان اندازه سریع و یا اغلب سریع تر از هیپ فیبونانچی برای این کاربرد هستند. <ref>{{citation
+[[الگوریتم دیکسترا]] برای [[مسئله یافتن کوتاهترین مسیر | یافتن کوتاهترین مسیر]] در گراف ها و [[الگوریتم پریم]] برای [[درخت فراگیر مینیمم]]، هر دو از مین هیپ استفاده می کنند که در آن {{math|''n''}} عملیات حذف مینیمم و {{math|''m''}} عملیات کاهش اولویت وجود دارد. که     {{math|''n''}} تعداد رئوس در گراف و  ''m'' تعداد یال ها است. با استفاده از یک هیپ {{math|''d''}} تایی با <math>{ n / m = d }</math> {{چر}} کل زمان برای این دو نوع عملیات ممکن است متعادل شود که کل زمان برای الگوریتم برابر می شود با <math>{(n_{n/m}gol m)O}</math> {{چر}}. زمان اجرای بهبود یافته هیپ دودویی این الگوریتم ها وقتی که تعداد یال ها به طور قابل ملاحظه ای بیشتر از تعداد راس ها باشد، برابر است با <math>{(n gol m)O}</math> .<ref name="j75"/><ref name="t2">{{harvtxt|Tarjan|1983}}, pp. 77 and 91.</ref> یک ساختمان داده صف اولویت دیگر، [[هیپ فیبوناتچی]] است که زمان اجرای نظری بهتر <math>{(n gol n + m)O}</math> را می دهد. ولی در عمل، به طور کلی هیپ {{math|''d''}}تایی ها حداقل به همان اندازه سریع و یا اغلب سریع تر از هیپ فیبونانچی برای این کاربرد هستند. <ref>{{citation
  | last1 = Cherkassky | first1 = B. V.
  | last2 = Goldberg | first2 = A. V.
@@ خط ۵۲: / خط ۸۴: @@
  | publisher = Addison-Wesley
  | title = Data Structures and Algorithm Analysis
- | year = 2007}}.</ref> علاوه بر این، معمولا هیپ های {{math|''d''}}تایی بسیار سریع تر از هیپ دودویی اجرا می شود. به خاطر اندازه هیپ که بیشتر از اندازه [[حافظه نهان]] کامپیوتر است. هیپ دودویی معمولا به [[cache miss]] بیشتر و [[page faults]] [[حافظه مجازی]] بیشتری نسبت به هیپ {{math|''d''}}تایی نیاز دارد.
+ | year = 2007}}.</ref> علاوه بر این، معمولا هیپ های {{math|''d''}}تایی بسیار سریع تر از هیپ دودویی اجرا می شود. به خاطر اندازه هیپ که بیشتر از اندازه [[حافظه نهان]] کامپیوتر است. هیپ دودویی معمولا به [[کش سی‌پی‌یو]] بیشتر و page fault [[حافظه مجازی]] بیشتری نسبت به هیپ {{math|''d''}}تایی نیاز دارد. <ref name="nmm91">{{citation
+ | last1 = Naor | first1 = D.
+ | last2 = Martel | first2 = C. U.
+ | last3 = Matloff | first3 = N. S.
+ | year = 1991
+ | doi = 10.1093/comjnl/34.5.428
+ | issue = 5
+ | journal = Computer Journal
+ | pages = 428–437
+ | title = Performance of priority queue structures in a virtual memory environment
+ | volume = 34}}.</ref><ref name="k10">{{citation
+ | last = Kamp | first = Poul-Henning
+ | journal = ACM Queue
+ | title = You're doing it wrong
+ | url = http://queue.acm.org/detail.cfm?id=1814327
+ | volume = 8
+ | issue = 6
+ | year = 2010}}.</ref>
@@ خط ۵۸: / خط ۱۰۸: @@
 == منابع ==
 <!--- [[ویکی‌پدیا:پانویس‌ها]] را بخوانید. در وسط مقاله از <ref>منبع</ref> به عنوان منبع استفاده کنید -->
-http://en.wikipedia.org/wiki/D-ary_heap
 {{پانویس}}
+http://en.wikipedia.org/wiki/D-ary_heap
 == پیوند به بیرون ==
 *[https://github.com/valyala/gheap C++ implementation of generalized heap with D-Heap support]
 <!--- رده‌بندی --->
 {{انبار-رده|Algorithms}}
+{{DEFAULTSORT:D-Ary Heap}}
-[[رده:الگوریتم‌ها]]
+[[Category:Heaps (data structures)]]
 [[رده:مقاله‌های ایجاد شده توسط ایجادگر]]
 <!--- میان‌ویکی را وارد کنید مثل [[en:Article]] --->
 [[en:Article]]
+[[pl:Kopiec a-arny]]