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

در علوم رایانه، صف اولویت دار دوطرفه یا هرم دوطرفه ( به انگلیسی: DEPQ ) داده ساختاری شبیه هرم یا صف دوطرفه می باشد که برای حذف عضو کمینه و بیشینه بهینه است. هر عضو در صف اولویت دار دوطرفه دارای یک اولویت یا ارزش می باشد و می توان عناصر را به ترتیب صعودی یا نزولی با پیچیدگی زمانی برابر، حذف کرد.
( ) isEmpty
چک می کند صف خالی است یا نه و اگر خالی بود مقدار درست ( به انگلیسی: true ) برمی گرداند.
( ) size
تعداد کل عناصر موجود در صف را برمی گرداند.
( ) getMin
عنصر با اولویت کمینه را برمی گرداند.
( ) getMax
عنصر با اولویت بیشینه را برمی گرداند.
x ) put )
عنصر x را به صف اضافه می کند.
( ) removeMin
عنصر با اولویت کمینه را حذف می کند و آن را بازمی گرداند.
( ) removeMax
عنصر با اولویت بیشینه را حذف می کند و آن را بازمی گرداند. اگر عملیاتی بر دو عنصر با اولویت یکسان اجرا شود، اولویت با عنصری است که ابتدا وارد شده است.
صف اولویت دار دوطرفه می تواند با درخت دودویی جستجو متعادل ( به انگلیسی: balanced binary search trees ) یا داده ساختاری خاص مثل min - max heap و pairing heap پیاده سازی شود.
دراین روش دو داده ساختار هرم کمینه و هرم بیشینه با عناصر یکسان داریم که هر دوعنصر یکسان در دو هرم به هم اشاره ( به انگلیسی: pointer ) می کنند.
در این روش، اگر عناصر را مرتب کنیم یکی در میان هنصرها در هرم بیشینه و کمینه نگه می داریم یعنی نصف عناصر در هرم کمینه و نصف دیگر هرم بیشینه قرار می گیرد و هر عنصر به عنصر بعدی خود - که بدیهی است در هرم دیگر قرار دارد – اشاره می کند.
دراین روش داده ساختار یک هرم است که هر گره در آن دوعضو دارد و براساس عضو اول هرم کمینه و براساس عضو دوم هرم بیشینه می باشد.
وقتی صف اولویت دار دوطرفه با هرم فاصله پیاده سازی شود و n عنصر داشته باشد پیچیدگی زمانی هر عملیات به شرح زیر است.
وقتی صف اولویت دار دوطرفه با هرم یا هرم جفت پیاده سازی شود پیچیدگی زمانی عملیات های مختلف به شرح زیر است. پیچیدگی زمانی برای هرم جفت به صورت سرشکن است.
یکی از کاربردهای مهم مرتب سازی خارجی است. ابتدا نیمه از داده ها را در صف اولویت دار دوطرفه می ریزیم حال باقی عناصر را یکی یکی می خوانیم و اگر آن عنصر کوچکتر مساوی عنصر کمینه در صف اولویت دار دوطرفه بود، آن را جزو عنصر دسته چپ و اگر بزرگتر مساوی عنصر بیشینه در صف اولویت دار دوطرفه بود، آن را در دسته راست قرار می دهیم در غیر این صورت عنصر کمینه یا بیشینه را حذف می کنیم. اگر عنصر کمینه را حذف کردیم عنصر جدید را به دسته راست و اگر عنصر کمینه را حذف کردیم عنصر جدید را به دسته چپ اضافه می کنیم. عناصر وجود در صف اولویت دار دوطرفه همان عناصر میانی مرتب شده هستند وعناصر چپ و راست را مرتب می کنیم.