Басым кезек


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Авалара CodeNation Голдман Сакс Google Microsoft
кезек теория

Басымдық құйрық - бұл қарапайым кезекке ұқсас, бірақ оның әрбір элементіне байланысты басымдығы бар мәліметтер құрылымының түрі. Элемент бұрынырақ басымдылыққа ие болады. Кейбір жағдайларда бірдей басымдылыққа ие екі элемент бар, содан кейін бірінші кезектелген элемент қызмет етеді.

мысал

Айталық, А және В жұмыс орындарының саны В-ға қарағанда жоғары, ал жұмыс В-ға қарағанда жоғары болады деп есептейік.

  1. A
  2. B
  3. A

Келесі кезекте кезек кезегі қалыптасады:

Басым кезек Басым кезек

Сонымен, бұл жерде сіз басымдығы жоғары жұмыс орындарының басымдылығы төмен жұмыс орындарының алдында тағайындалатынын көресіз.

Басым кезектің түрлері

  1. Тапсырыс кезегінің өсуі

    Бұл басымдылық_ кезегінің типінде басымдылығы төмен нөмір жоғары басымдылықтағы жұмыс орындарына тағайындалады.
    Мысалға: Егер А және В екі жұмысына 1 және 2 сандары берілсе, онда А жұмысының басымдығы жоғары болса, А-ға 1, ал В жұмысына 2 беріледі.

  2. Тапсырыс кезегінің кемуі

    Бұл басымдылық_ кезегінің типінде басымдығы жоғары жұмыс орындарына басымдықтың үлкен нөмірі беріледі.
    Мысалға: Егер А және В екі жұмысына 1 және 2 сандары берілсе, онда А жұмысының басымдығы жоғары болса, А-ға 2, ал В жұмысына 1 беріледі.

Басымдылық кезегі бойынша орындалатын операция

Басымдық_кветі бойынша орындалатын негізгі операциялар:

  1. Енгізу: Кезекке оның басымдығына сәйкес элементті салыңыз.
  2. Жою: Кезекті алып тастайды.
  3. getHighestPriority: Сізге ең маңызды элемент береді.

Priority_queue тағы бірнеше әрекеттерді қолдайды:

  1. Пик: Элементті кезектің алдында алыңыз.
  2. isFull: кезектің толғандығын тексереді.
  3. isEmpty: кезектің бос екендігін тексереді.

Бағдарламалар

  1. Процессорды жоспарлау, дискіні жоспарлау және т.с.с.
  2. Графикалық алгоритмдер (Дайкстра жолының ең қысқа алгоритмі, Примнің ең аз созылатын ағашы және т.б.)

Іске асыру

Басымдық кезегін массив, байланыстырылған тізім және т.с.с. сияқты әр түрлі деректер құрылымын қолдану арқылы жүзеге асыруға болады, кейбір мәліметтер құрылымдары уақыттың күрделілігімен төменде келтірілген:

  1. Массивтер (O (n * log (n)))
  2. Байланыстырылған тізім (O (n))
  3. Үйме (O (журнал (n)))

Деректер құрылымының ішінен үйінді деректер құрылымы басымдылық_күнін енгізу кезінде уақыттың ең жақсы күрделілігін қамтамасыз етеді.

Әдебиеттер тізімі