Кезектердің басымдығы бойынша түрі (Басымдық кезектері)

Кіріспе

Компьютерлік ғылымдағы абстрактілі дерек түрі

Компьютерлік ғылымда басымдық кезегі – бұл обыкновенды кезек немесе стек дерек құрылымына ұқсас абстрактілі дерек түрі. Басымдық кезегіндегі әрбір элементтің оған сәйкес басымдығы болады. Басымдық кезегінде жоғары басымдығы бар элементтер, төмен басымдығы бар элементтерге дейін қызмет көрсетеді. Кейбір жағдайларда, егер екі элементтің басымдығы бірдей болса, олар кезекке қосылған тәртіппен қызмет көрсетеді. Басқа жағдайларда, бірдей басымдығы бар элементтердің тәртібі белгісіз болуы мүмкін. Басымдық кезегі көбінесе үйінділерді пайдалана отырып іске асырылса да, олар үйінділерден түсінік тұрғысынан ерекшеленеді. Басымдық кезегі – тізім немесе карта сияқты абстрактілі дерек құрылымы; тізімді байланыстырылған тізіммен немесе массивпен іске асыруға болатыны сияқты, басымдық кезегін үйіндімен немесе басқа әдіспен, мысалы, реттелген массивпен іске асыруға болады.

Әдеттегі орындалу

Өнімділікті жақсарту үшін басымдық кезектері әдетте үйіндіге негізделген, енгізу және жою операциялары үшін O(log n) өнімділігін қамтамасыз етеді, ал n элементтер жиынтығынан бастапқы үйіндіні құру үшін O(n) уақыт кетеді. Жұптастырылған үйінділер немесе Фибоначчи үйінділері сияқты негізгі үйінді дерек құрылымының түрлері кейбір операциялар үшін жақсы шешімдер ұсынуы мүмкін. Басқа жағынан, өзін-өзі теңгертетін екілік іздеу ағашы қолданылғанда, енгізу және жою да O(log n) уақыт алады, бірақ элементтердің бар тізбегінен ағаштар құру O(n log n) уақытты қажет етеді; мұндай жағдайда үшінші тараптық немесе стандартты кітапханалар сияқты осы дерек құрылымдарына қол жеткізу мүмкін болады. Орындық күрделілікті қарастырғанда, байланысты тізіммен өзін-өзі теңгертетін екілік іздеу ағашын пайдалану көбірек жадты қажет етеді, себебі ол басқа түйіндерге қосымша сілтемелерді сақтауды талап етеді. Есептеу күрделілігі тұрғысынан, басымдық кезектері сұрыптау алгоритмдерімен сәйкес келеді. Басымдық кезектері мен сұрыптау алгоритмдерінің эквиваленттілігі туралы төмендегі бөлім тиімді сұрыптау алгоритмдерінің тиімді басымдық кезектерін қалай құра алатынын сипаттайды.

Арнайы үйінділер

Қосымша операцияларды қамтамасыз ететін немесе кілттердің белгілі бір түрлеріне, әсіресе бүтін кілттерге арналған үйіндіге негізделген іске асырулардан артық көрінетін бірнеше мамандандырылған үйінділік дерек құрылымдары бар. Мүмкін кілттер жиынтығы {1, 2, ..., C} деп есептейік. Егер тек insert, find min және extract min қажет болса және бүтін сан басымдықтары болған жағдайда, C байланысқан тізімдер массиві және бастапқыда C-ға тең болатын top көрсеткішінен букет кезекін құрастыруға болады. k кілтімен элементті енгізу, элементті k-шы тізімге қосады және top ← min(top, k) жаңартуын орындайды, екеуі де тұрақты уақытта жүзеге асады. Extract min, top индексі бар тізімнен бір элементті жойып, қайтарады, содан кейін бос емес тізімге көрсеткіш қайтадан бағытталғанша top-ты арттырады; ең жаман жағдайда бұл O(C) уақытын алады. Бұл кезектер графтың төбелерін олардың дәрежесі бойынша сұрыптау үшін пайдалы. Ван Эмде Боас ағашы minimum, maximum, insert, delete, search, extract min, extract max, predecessor және successor] операцияларын O(log log C) уақытында қолдайды, бірақ кішкентай кезектер үшін кеңістік шығындары шамамен O(2^(m/2) ) құрайды, мұнда m – басымдық мәніндегі биттер саны. Хеш функциясын қолдану арқылы кеңістіктің көлемін айтарлықтай азайтуға болады. Фредман мен Уиллардтың Fusion ағашы minimum операциясын O(1) уақытында, ал insert және extract min операцияларын белгілі бір уақытта іске асырады. Алайда автордың айтуынша, "Біздің алгоритмдеріміз тек теориялық қызығушылық тудырады; орындалу уақытына қатысты тұрақты факторлар практикалық қолдануға мүмкіндік бермейді". Егер әрбір "extract min" операциясына көптеген "peek" операциялары орындалса, барлық ағаш және үйінділік іске асыруларда peek әрекеттерінің уақыт күрделілігі әрбір енгізу мен жоюдан кейін ең жоғары басымдықты элементті кэштеу арқылы O(1) дейін төмендетілуі мүмкін. Ендірілу үшін бұл ең көп дегенде тұрақты шығындарды қосады, өйткені жаңадан енгізілген элемент тек бұрын кэштелген минималды элементпен салыстырылады. Жою үшін бұл ең көп дегенде өшіру шығынынан арзан болатын қосымша "peek" шығынын қосады, сондықтан жалпы уақыт күрделілігі айтарлықтай өзгереді. Монотонды басымдық кезектері – бұрын алынған элементтерден төмен басымдыққа ие элементтер ешқашан енгізілмейтін жағдайда оңтайландырылған мамандандырылған кезектер. Бұл шектеу басымдық кезектерінің көптеген практикалық қолдануларында орындалады.

There are several specialized heap data structures that either supply additional operations or outperform heap based implementations for specific types of keys, specifically integer keys. Suppose the set of possible keys is {1, 2, , C}. When only insert, find min and extract min are needed and in case of integer priorities, a bucket queue can be constructed as an array of C linked lists plus a pointer top, initially C. Inserting an item with key k appends the item to the k'th list, and updates top ← min(top, k), both in constant time. Extract min deletes and returns one item from the list with index top, then increments top if needed until it again points to a non empty list; this takes O(C) time in the worst case. These queues are useful for sorting the vertices of a graph by their degree. A van Emde Boas tree supports the minimum, maximum, insert, delete, search, extract min, extract max, predecessor and successor] operations in O(log log C) time, but has a space cost for small queues of about O(2m/2), where m is the number of bits in the priority value. The space can be reduced significantly with hashing. The Fusion tree by Fredman and Willard implements the minimum operation in O(1) time and insert and extract min operations in time. However it is stated by the author that, "Our algorithms have theoretical interest only; The constant factors involved in the execution times preclude practicality." For applications that do many "peek" operations for every "extract min" operation, the time complexity for peek actions can be reduced to O(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. For insertion, this adds at most a constant cost, since the newly inserted element is compared only to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is typically cheaper than the deletion cost, so overall time complexity is not significantly impacted. Monotone priority queues are specialized queues that are optimized for the case where no item is ever inserted that has a lower priority (in the case of min heap) than any item previously extracted. This restriction is met by several practical applications of priority queues.

Басымдық кезегін құру үшін сұрыптау алгоритмін қолдану

Сорттау алгоритмі басымдық кезегін іске асыру үшін де қолданылуы мүмкін. Атап айтқанда, Торуп былай дейді: Біз басымдық кезектерінен сұрыптауға жалпы детерминистік сызықтық кеңістіктегі азайтуды ұсынамыз, яғни егер біз n кілтті S(n) уақытта сұрыптай алсақ, онда O(S(n)) уақытында өшіру және енгізуді қолдайтын, ал ең кіші элементті тұрақты уақытта табатын басымдық кезегі болады. Демек, егер кілт бойынша O(S) уақытында сұрыптай алатын сұрыптау алгоритмі болса, мұнда S – n және сөз өлшемінің функциясы, онда берілген процедураны пайдаланып жоғары басымдылыққа ие элементті O(1) уақытта алуға болатын, ал жаңа элементтерді енгізу (және элементтерді жою) O(S) уақытын алатын басымдық кезегін құруға болады. Мысалы, егер O(n log n) сұрыптау алгоритмі болса, онда O(1) уақытта алуға және O(log n) уақытта енгізуге болатын басымдық кезегін құруға болады.

Кітапханалар

Басымдық кезегі көбінесе "контейнерлік дерек құрылымы" деп саналады. Стандартты үлгілер кітапханасы (STL) және C++ 1998 стандарты std::priority_queue-ді STL контейнерлік адаптер кластарының бір үлгісі ретінде анықтайды. Алайда, ол бірдей басымдықты екі элементке қалай қызмет көрсету керектігін нақтыламайды, және шын мәнінде, көптеген іске асырулар оларды кезектегі орналасу ретімен қайтармайды. Ол максималды басымдық кезегін іске асырады және үш параметрі бар: сұрыптау үшін салыстыру объектісі, мысалы, функциялық объект (белгіленбесе less<T> болады), дерек құрылымдарын сақтау үшін негізгі контейнер (белгіленбесе std::vector<T> болады) және тізбектің басы мен соңына итераторлар. Нақты STL контейнерлерінен айырмашылығы, ол элементтерін итерациялауға мүмкіндік бермейді (ол дерек типінің абстрактілік анықтамасына қатаң сәйкес келеді). STL сонымен қатар, кездейсоқ кіру контейнерін бинарлық максималды үйінді ретінде басқаруға арналған қосымша функцияларды қамтиды. Boost кітапханаларында да heap кітапханасы бар. Python-ның heapq модулі тізім үстінде бинарлық минималды үйіндіні іске асырады. Java кітапханасында бинарлық үйінді ретінде минималды басымдық кезегін іске асыратын класс бар. .NET кітапханасында массив негізіндегі төртіншілік минималды үйіндіні іске асыратын PriorityQueue класы бар. Scala кітапханасында максималды басымдық кезегін іске асыратын PriorityQueue класы бар. Go кітапханасында кез келген үйлесімді дерек құрылымының үстінде минималды үйіндіні іске асыратын container/heap модулі бар. Стандартты PHP кітапханасының кеңейтуінде SplPriorityQueue класы бар. Apple-дың Core Foundation фреймворкі минималды үйіндіні іске асыратын CFBinaryHeap құрылымын қамтиды.

Жазылу диапазонын басқару

Басымдық кезектерін желілік маршрутизатордан берілу желісіндегі өткізу қабілеті сияқты шектеулі ресурстарды басқару үшін пайдалануға болады. Егер шығу трафигі жеткіліксіз өткізу қабілетіне байланысты кезекке тұрса, барлық басқа кезектер тоқтатылып, ең жоғары басымдыққа ие кезектегі трафик келген кезде жіберіледі. Бұл басымдық берілген трафиктің (мысалы, нақты уақыт трафигі, мысалы, VoIP қосылымының RTP ағыны) ең аз кешігумен және кезек максималды сыйымдылығына жеткендіктен бас тарту ықтималдығының ең төмен болуын қамтамасыз етеді. Барлық басқа трафик ең жоғары басымдыққа ие кезек бос болған кезде өңделеді. Тағы бір тәсіл – жоғары басымдыққа ие кезектерден пропорционалды түрде көп трафик жіберу. Көптеген қазіргі заманғы жергілікті желілер протоколдары медиаға қол жеткізуді басқару (MAC) қосалқы қабатында басымдық кезектерін ұғымын қамтиды, бұл жоғары басымдылықты қолданбалардың (мысалы, VoIP немесе IPTV) ең жақсы күшпен қызмет көрсетілетін басқа қолданбаларға қарағанда төмен кешігуді сезінуін қамтамасыз етеді. Мысалдарға IEEE 802.11e (қызмет сапасын қамтамасыз ететін IEEE 802.11 толықтыруы) және ITU T G. hn (бұрыннан бар үй сымдарын (электр желілері, телефон желілері және коаксиалдық кабельдерді) пайдаланатын жоғары жылдамдықты жергілікті желілер стандарты) жатады. Әдетте, жоғары басымдықты пакеттердің барлық басқа трафиктің өтуін тоқтатуын болдырмау үшін, ең жоғары басымдыққа ие кезектегі трафиктің өткізу қабілетін шектеу үшін шектеу (полицер) орнатылады. Бұл шек әдетте жоғары деңгейдегі басқару жүйелері, мысалы Cisco Callmanager, арқылы бағдарламаланған өткізу қабілеті шегінен асып кететін қоңырауларды тежеуге мүмкіндік береді.

Дикстра алгоритмі

График жабылас тізім немесе матрица түрінде сақталғанда, Дикстра алгоритмін іске асыру кезінде ең кішкентай мәнді тиімді алу үшін басымдық кезегін қолдануға болады, бірақ басымдық кезегіндегі нақты бір төбеге берілген басымдықты тиімді түрде өзгерту қабілеті де қажет. Егер график түйін объектілері түрінде сақталса және басымдық түйін жұптары қалыпқа (heap) енгізілсе, кірген түйіндерді қадағаласа, нақты бір төбеге берілген басымдықты өзгертудің қажеті жоқ. Түйінге кіргеннен кейін, егер ол қайтадан қалыпқа түсіп қалса (бұрын оған кішкентайрақ басымдық саны тағайындалған болса), ол алынып тасталады және назардан тыс қалдырылады.

Хаффман коды

Хаффман кодтауы ең төмен жиілікті екі ағашты қайта-қайта алуды қажет етеді. Басымдық кезектері осыны іске асырудың бір жолы.

Ең жақсы бірінші іздеу алгоритмдері

Ең жақсы бірінші іздеу алгоритмдері, A* іздеу алгоритмі сияқты, салмақты графтың екі төбесі немесе түйіні арасындағы ең қысқа жолды іздейді, ең перспективалы маршруттарды бірінші болып қарастырады. Зерттелмеген маршруттарды қадағалау үшін басымдық кезегі (немесе фриндж) қолданылады; жалпы жол ұзындығының естімі (A* жағдайында – төменгі шек) ең кішкентай болған маршрутқа ең жоғары басымдық беріледі. Егер жадтың жеткіліксіздігі ең жақсы бірінші іздеуді қолдануға қолайсыз жағдайға келтірсе, SMA* алгоритмі сияқты түрлендірілген нұсқаларды пайдалануға болады, олар төмен басымдыққа ие элементтерді жоюға мүмкіндік беретін екі жақты басымдық кезегін қолданады.

ROAM триангуляциялау алгоритмі

Нақты уақыт режимінде оптималды бейімделетін торлар (ROAM) алгоритмі жердің динамикалық түрде өзгеретін үшбұрыштық торларын есептейді. Ол қажет болған жерде үшбұрыштарды бөліп, қажеттілік азайған жерде біріктіру арқылы жұмыс істейді. Алгоритм жер бедеріндегі әрбір үшбұрышқа басымдық тағайындайды, әдетте бұл үшбұрыштың бөлінуінен қателік қанша азаятынымен байланысты болады. Алгоритм екі басымдық кезегін пайдаланады: біреуі бөлінетін үшбұрыштар үшін, екіншісі біріктірілетін үшбұрыштар үшін. Әр қадамда бөлу кезегінен ең жоғары басымдыққа ие үшбұрыш бөлінеді немесе біріктіру кезегінен ең төмен басымдыққа ие үшбұрыш көршілес үшбұрыштармен біріктіріледі.

Минималды аралық ағашты Prim алгоритмі

Prim алгоритмінде min heap басымдық кезегін қолдану арқылы байланысты және бағытталмаған графтың ең кішкентай аралықтағы ағашын табуға болады, бұл тиімді жұмыс уақытын қамтамасыз етеді. Бұл min heap басымдық кезегі min heap дерек құрылымын пайдаланады, ол кірістіру, ең кішкентайды табу, ең кішкентайын алу және кілтті азайту сияқты операцияларды қолдайды. Осы іске асыруда қабырғалардың салмағы түйіндердің басымдығын анықтау үшін пайдаланылады. Салмақ неғұрлым төмен болса, басымдық соғұрлым жоғары, ал салмақ неғұрлым жоғары болса, басымдық соғұрлым төмен болады.

Параллель басымдық кезегі

Параллельдеуді басымдық кезегін жылдамдату үшін қолдануға болады, бірақ басымдық кезегі интерфейсіне кейбір өзгерістер қажет. Мұндай өзгерістердің себебі – тізбекті жаңарту әдетте тек O(1) немесе O(log n) шығынды, және мұндай операцияны параллельдеудің ешқандай практикалық пайдасы жоқ. Мүмкін болатын бір өзгеріс – бірнеше процессордың бір уақытта бір басымдық кезегіне қол жеткізуіне рұқсат беру. Екінші мүмкін өзгеріс – бір элемент емес, бірнеше элементпен жұмыс істейтін топтық операцияларды рұқсат ету. Мысалы, extractMin ең жоғары басымдыққа ие алғашқы k элементті жояды.

Бір мезгілдегі қатарлы қолжетімділік

Егер басымдық кезегі бір мезгілде қол жеткізуге мүмкіндік берсе, бірнеше процестер сол басымдық кезегінде бір мезгілде операцияларды орындай алады. Алайда, бұл екі мәселені тудырады. Біріншіден, жеке операциялардың семантикасының анықтамасы енді айқын емес. Мысалы, егер екі процесс ең жоғары басымдықты элементті алуды қаласа, олар бірдей элементті алу керек пе, әлде әртүрлі элементтерді алу керек пе? Бұл басымдық кезегін пайдалана отырып, бағдарлама деңгейіндегі параллелизмді шектейді. Сонымен қатар, бірнеше процесс бір элементке қол жеткізе алатындықтан, бұл қақтығысқа әкеледі. Басымдық кезегіне бір мезгілде қол жеткізу бір мезгілде оқу, бір мезгілде жазу (CRCW) PRAM моделінде жүзеге асырылуы мүмкін. Келесі бөлімде басымдық кезегі өткізіп жіберу тізімі ретінде жүзеге асырылады. Сонымен қатар, өткізіп жіберу тізімін құлыптаудан босату үшін атомдық синхрондау примитиві, CAS қолданылады. Өткізіп жіберу тізімінің түйіндері бірегей кілт, басымдық, әрбір деңгей үшін келесі түйіндерге сілтемелер массиві және жою белгісінен тұрады. Жою белгісі түйіннің процесспен жойылатынын көрсетеді. Бұл басқа процестердің жоюға тиісті түрде жауап беруіне мүмкіндік береді. insert(e): Бірінші, кілті мен басымдығы бар жаңа түйін құрылады. Сонымен қатар, түйінге деңгейлер саны беріледі, бұл көрсеткіштер массивінің мөлшерін анықтайды. Содан кейін жаңа түйін енгізу үшін дұрыс орынды табу үшін іздеу жүргізіледі. Іздеу бірінші түйінен және ең жоғары деңгейден басталады. Содан кейін, дұрыс орын табылғанға дейін, өткізіп жіберу тізімі төменгі деңгейге дейін қарастырылады. Іздеу кезінде әрбір деңгей үшін соңғы қарастырылған түйін сол деңгейдегі жаңа түйін үшін аталық түйін ретінде сақталады. Сонымен қатар, аталық түйіннің көрсеткіші сол деңгейде көрсететін түйін сол деңгейдегі жаңа түйіннің ізбасары ретінде сақталады. Содан кейін, жаңа түйіннің әрбір деңгейі үшін аталық түйіннің көрсеткіштері жаңа түйінге орнатылады. Соңында, жаңа түйіннің әрбір деңгейі үшін көрсеткіштер тиісті ізбасар түйіндерге орнатылады. extract min: Бірінші, жою белгісі орнатылмаған түйінге жеткенше өткізіп жіберу тізімі қарастырылады. Бұл жою белгісі сол түйін үшін true деп орнатылады. Соңында, жойылған түйіннің аталық түйіндерінің көрсеткіштері жаңартылады. Егер басымдық кезегіне бір мезгілде кіруге рұқсат берілсе, екі процесс арасында қақтығыс туындауы мүмкін. Мысалы, егер бір процесс жаңа түйін енгізуге тырысса, бірақ бір уақытта басқа процесс сол түйіннің алдыңғысын жоюға дайын болса, қақтығыс туындайды. Осы бөлімнің қалған бөлігінде бөлінген жадтағы кезекке негізделген алгоритм талқыланады. Әрбір процессордың өзінің жергілікті жады және жергілікті (тізбекті) басымдық кезегі бар деп есептейміз. Жаһандық (параллельді) басымдық кезегінің элементтері барлық процессорларға таратылады. k insert операциясы элементтерді жергілікті кезектерге енгізетін процессорларға біркелкі түрде кездейсоқ түрде жібереді. Бір элементті кезекке әлі де қосуға болатынын ескеріңіз. Бұл стратегияны қолдану арқылы, әрбір процессордың ең кіші элементтері жоғары ықтималдылықпен жергілікті элементтерінің бірінде болады. Осылайша, әрбір процессор жаһандық басымдық кезегінің өкілдік бөлігін сақтайды. Бұл қасиет k extract min орындалғанда қолданылады, өйткені әрбір жергілікті кезектің ең кіші элементтері алынып тасталады және нәтиже жиынтығына жиналады. Нәтиже жиынтығының элементтері әлі де олардың бастапқы процессорларымен байланысты. Әрбір жергілікті кезектен алынып тасталатын элементтердің саны процессорлардың санына және k-ға байланысты. Параллель таңдау арқылы нәтиже жиынтығының ең кіші элементтері анықталады. Бұл элементтер әлемдегі ең кішкентай элементтер болуы ықтималдығы жоғары. Егер жоқ болса, элементтер әрбір жергілікті кезектен қайта алынып, нәтиже жиынтығына енгізіледі. Бұл нәтиже жиынтығында ең кіші элементтер болғанға дейін жалғасады. Енді осы элементтерді қайтаруға болады. Нәтиже жиынтығының барлық басқа элементтері олардың жергілікті кезектеріне қайта енгізіледі. k extract min операциясының орындалу уақыты күтіледі , мұндағы және - басымдық кезегінің мөлшері. Басымдық кезегін k extract min операциясынан кейін нәтиже жиынтығының қалған элементтерін тікелей жергілікті кезектерге жылжытпай, одан әрі жақсартуға болады. Бұл элементтерді нәтиже жиынтығы мен жергілікті кезектер арасында жылжытуды үнемі сақтаудан сақтайды. Бірнеше элементті бірден алып тастау арқылы айтарлықтай жылдамдыққа қол жеткізуге болады. Бірақ барлық алгоритмдер осы түпкілікті басымдық кезегін пайдалана алмайды. Мысалы, Дийкстра алгоритмі бірнеше түйінде бірден жұмыс істей алмайды. Алгоритм басымдық кезегінен ең кішкентай қашықтығы бар түйінді алып, оның барлық көрші түйіндері үшін жаңа қашықтықтарды есептейді. Егер сіз бірнеше түйінді алсаңыз, бір түйінде жұмыс істеу басқа бір түйіннің қашықтығын өзгерте алады. Сондықтан k элементтік операциялар Дийкстра алгоритмінің белгілеу қасиетін жояды.

If the priority queue allows concurrent access, multiple processes can perform operations concurrently on that priority queue. However, this raises two issues. First of all, the definition of the semantics of the individual operations is no longer obvious. For example, if two processes want to extract the element with the highest priority, should they get the same element or different ones? This restricts parallelism on the level of the program using the priority queue. In addition, because multiple processes have access to the same element, this leads to contention. The concurrent access to a priority queue can be implemented on a Concurrent Read, Concurrent Write (CRCW) PRAM model. In the following the priority queue is implemented as a skip list. In addition, an atomic synchronization primitive, CAS, is used to make the skip list lock free. The nodes of the skip list consists of a unique key, a priority, an array of pointers, for each level, to the next nodes and a delete mark. The delete mark marks if the node is about to be deleted by a process. This ensures that other processes can react to the deletion appropriately. insert(e): First, a new node with a key and a priority is created. In addition, the node is assigned a number of levels, which dictates the size of the array of pointers. Then a search is performed to find the correct position where to insert the new node. The search starts from the first node and from the highest level. Then the skip list is traversed down to the lowest level until the correct position is found. During the search, for every level the last traversed node will be saved as parent node for the new node at that level. In addition, the node to which the pointer, at that level, of the parent node points towards, will be saved as the successor node of the new node at that level. Afterwards, for every level of the new node, the pointers of the parent node will be set to the new node. Finally, the pointers, for every level, of the new node will be set to the corresponding successor nodes. extract min: First, the skip list is traversed until a node is reached whose delete mark is not set. This delete mark is than set to true for that node. Finally the pointers of the parent nodes of the deleted node are updated. If the concurrent access to a priority queue is allowed, conflicts may arise between two processes. For example, a conflict arises if one process is trying to insert a new node, but at the same time another process is about to delete the predecessor of that node. The rest of this section discusses a queue based algorithm on distributed memory. We assume each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors. A k insert operation assigns the elements uniformly random to the processors which insert the elements into their local queues. Note that single elements can still be inserted into the queue. Using this strategy the global smallest elements are in the union of the local smallest elements of every processor with high probability. Thus each processor holds a representative part of the global priority queue. This property is used when k extract min is executed, as the smallest elements of each local queue are removed and collected in a result set. The elements in the result set are still associated with their original processor. The number of elements that is removed from each local queue depends on and the number of processors

By parallel selection the smallest elements of the result set are determined. With high probability these are the global smallest elements. If not, elements are again removed from each local queue and put into the result set. This is done until the global smallest elements are in the result set. Now these elements can be returned. All other elements of the result set are inserted back into their local queues. The running time of k extract min is expected , where and is the size of the priority queue. The priority queue can be further improved by not moving the remaining elements of the result set directly back into the local queues after a k extract min operation. This saves moving elements back and forth all the time between the result set and the local queues. By removing several elements at once a considerable speedup can be reached. But not all algorithms can use this kind of priority queue. Dijkstra's algorithm for example can not work on several nodes at once. The algorithm takes the node with the smallest distance from the priority queue and calculates new distances for all its neighbor nodes. If you would take out nodes, working at one node could change the distance of another one of the nodes. So using k element operations destroys the label setting property of Dijkstra's algorithm.