پشته کی‌دی

پشته کی‌دی یک ساختار داده در علوم رایانه است که یک صف اولویت چند بعدی را بدون نیاز به فضای اضافی پیاده سازی می‌کند. این حالت تعمیم پشته است که امکان درج صحیح ، پرس و جو از حداقل عنصر و حذف حداقل عنصر را در هر یک از ابعاد 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) برای برنامه‌هایی با ابعاد بسیار زیاد کاربردی نیستند.

منابع

1. 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
2. ^ Advanced Data Structures, Peter Brass, ISBN 978-0-521-88037-4, page 270