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

در علوم رایانه، صف اولویت دار دوطرفه یا هرم دوطرفه  داده ساختاری شبیه هرم یا صف دوطرفه می‌باشد که برای حذف عضو کمینه و بیشینه بهینه است. هر عضو در صف اولویت دار دوطرفه دارای یک اولویت یا ارزش می‌باشد و می‌توان عناصر را به ترتیب صعودی یا نزولی با پیچیدگی زمانی برابر، حذف کرد.Data Structures, Algorithms, & Applications in Java: Double-Ended Priority Queues, Sartaj Sahni, 1999.

 عملیات‌ها 
()isEmpty

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

()size

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

()getMin

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

()getMax

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

x)put)

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

()removeMin

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

()removeMax

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

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

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

 تناظر کلی (به انگلیسی: Total correspondence) 
در این روش، اگر عناصر را مرتب کنیم یکی در میان هنصرها در هرم بیشینه و کمینه نگه می‌داریم یعنی نصف عناصر در هرم کمینه و نصف دیگر هرم بیشینه قرار می‌گیرد و هر عنصر به عنصر بعدی خود - که بدیهی است در هرم دیگر قرار دارد – اشاره می‌کند.
بندانگشتی|

 هرم ورودی (به انگلیسی: Interval heaps) 
دراین روش داده ساختار یک هرم است که هر گره در آن دوعضو دارد و براساس عضو اول هرم کمینه و براساس عضو دوم هرم بیشینه می‌باشد.
بندانگشتی|

 پیچیدگی زمانی 
وقتی صف اولویت دار دوطرفه با هرم فاصله پیاده‌سازی شود و 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)

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

 منابع 

رده:صف‌های اولویت‌دار
رده:نوع داده انتزاعی
رده:ویکی‌سازی رباتیک
رده:هرم‌ها (علوم رایانه)