صف اولویت‌دار دوطرفه

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از صف الویت دار دوطرفه)
پرش به ناوبری پرش به جستجو

در علوم رایانه، صف اولویت دار دوطرفه یا هرم دوطرفه (به انگلیسی: DEPQ) داده ساختاری شبیه هرم یا صف دوطرفه می‌باشد که برای حذف عضو کمینه و بیشینه بهینه است. هر عضو در صف اولویت دار دوطرفه دارای یک اولویت یا ارزش می‌باشد و می‌توان عناصر را به ترتیب صعودی یا نزولی با پیچیدگی زمانی برابر، حذف کرد.

عملیات‌ها[ویرایش]

()isEmpty

چک می‌کند صف خالی است یا نه و اگر خالی بود مقدار درست (به انگلیسی: true) برمی‌گرداند.

()size

تعداد کل عناصر موجود در صف را برمی‌گرداند.

()getMin

عنصر با اولویت کمینه را برمی‌گرداند.

()getMax

عنصر با اولویت بیشینه را برمی‌گرداند.

x)put)

عنصر x را به صف اضافه می‌کند.

()removeMin

عنصر با اولویت کمینه را حذف می‌کند و آن را بازمی‌گرداند.

()removeMax

عنصر با اولویت بیشینه را حذف می‌کند و آن را بازمی‌گرداند. اگر عملیاتی بر دو عنصر با اولویت یکسان اجرا شود، اولویت با عنصری است که ابتدا وارد شده‌است.

پیاده‌سازی[ویرایش]

صف اولویت دار دوطرفه می‌تواند با درخت دودویی جستجو متعادل (به انگلیسی: balanced binary search trees) یا داده ساختاری خاص مثل min-max heap و pairing heap پیاده‌سازی شود.

روش ساختار دوتایی[ویرایش]

دراین روش دو داده ساختار هرم کمینه و هرم بیشینه با عناصر یکسان داریم که هر دوعنصر یکسان در دو هرم به هم اشاره (به انگلیسی: pointer) می‌کنند.

Dual heap.jpg

تناظر کلی (به انگلیسی: Total correspondence)[ویرایش]

در این روش، اگر عناصر را مرتب کنیم یکی در میان هنصرها در هرم بیشینه و کمینه نگه می‌داریم یعنی نصف عناصر در هرم کمینه و نصف دیگر هرم بیشینه قرار می‌گیرد و هر عنصر به عنصر بعدی خود - که بدیهی است در هرم دیگر قرار دارد – اشاره می‌کند.

Total correspondence heap.jpg

هرم ورودی (به انگلیسی: Interval heaps)[ویرایش]

دراین روش داده ساختار یک هرم است که هر گره در آن دوعضو دارد و براساس عضو اول هرم کمینه و براساس عضو دوم هرم بیشینه می‌باشد.

Interval heap depq.jpg

پیچیدگی زمانی[ویرایش]

وقتی صف اولویت دار دوطرفه با هرم فاصله پیاده‌سازی شود و n عنصر داشته باشد پیچیدگی زمانی هر عملیات به شرح زیر است.

عملیات پیچیدگی زمانی
init() O(n)
isEmpty() O(1)
getmin() O(1)
getmax() O(1)
size() O(1)
insert(x) O(log n)
removeMin() O(log n)
removeMax() O(log n)

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

عملیات پیچیدگی زمانی
isEmpty() O(1)
getmin() O(1)
getmax() O(1)
insert(x) O(log n)
removeMax() O(log n)
removeMin() O(log n)

کاربرد[ویرایش]

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

منابع[ویرایش]