K-d heap

برخی از ویرایش‌ها در این مقاله در چارچوب یک تکلیف دانشگاهی انجام شده‌اند. این تکالیف توسط ؟ برای دانشجویان ؟ تعیین شده‌اند.

خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد.

((پشته (K-D))

پشته ( K-D ) یک ساختار داده در علوم کامپیوتر است که یک صف اولویت چند بعدی را بدون نیاز به فضای اضافی پیاده سازی می کند. این حالت تعمیم پشته است که امکان درج صحیح ، پرس و جو از حداقل عنصر و حذف حداقل عنصر را در هر یک از ابعاد k فراهم می کند و بنابراین شامل پشته دو سر به عنوان یک مورد خاص می شود.

ساختار

با توجه به مجموعه‌ای از n عضو ، که در آن هر کدام k کلید دارند، پشته (K-D) آنها را در یک درخت دودویی سازماندهی می‌کند که مستلزم دو شرط است:

1- این یک درخت دودویی کامل است، به این معنی که پر است احتمالاً به جز آخرین لایه، جایی که باید از سمت چپ پر شود.

2- مستلزم ترتیب پشته (K-D) است.

خاصیت ترتیب پشته (K-D) مشابه خاصیت پشته برای پشته های معمولی است. یک پشته نظم پشته (K-D) را حفظ می کند اگر:

گره در ریشه دارای اولین و کوچکترین ویژگی کل درخت باشد.

هر گره دیگر (V) که ریشه نیست، به گونه‌ای است که پدر آن (W) کوچک ‌ترین ویژگی I ام را از زیردرختی که توسط پدر ریشه دارد، داشته باشد، آنگاه (V) دارای کوچک‌ ترین (I mod k)+1 امین ویژگی از کل زیردرخت ریشه ‌دار با (V) را دارد.

یکی از پیامدهای این ساختار این است که اولین ویژگی کوچکترین عنصر به طور عادی در ریشه خواهد بود، و علاوه بر این همه کوچکترین ویژگی عناصر I ام برای هر I در اولین سطح k قرار خواهند داد.

عملیات

ایجاد یک پشته (K-D) از n عضو مرتبه زمانی O(n) دارد. و در طی آن عملیات زیر اجرا می شوند:

1- درج یک عنصر جدید در زمان O (log n)

2- عنصر را با یک کلید حداقل در هر یک از ابعاد در زمان ثابت برگردانید

3- حذف یک عنصر با حداقل کلید در هر بعد در زمان O(log n)

4- حذف یا تغییر یک عضو دلخواه در پشته در زمان O(log n) با فرض اینکه موقعیت آن در پشته مشخص باشد

نکته مهم، ثابت پنهان در این عملیات ها به طور نمایی که k )تعداد ابعاد( باشد بزرگ است، بنابراین پشته‌های (K-D) برای برنامه‌هایی با ابعاد بسیار زیاد کاربردی نیستند.

منابع

Ding Y., Weiss M.A. (1993) The K-D heap: An efficient multi-dimensional priority queue. In: Dehne F., Sack JR., Santoro N., Whitesides S. (eds) Algorithms and Data Structures. WADS 1993. Lecture Notes in Computer Science, vol 709. Springer, Berlin, Heidelberg
^ Advanced Data Structures, Peter Brass, ISBN 978-0-521-88037-4, page 270

This article "K-d heap" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:K-d heap. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.