Приоритетна Опашка

Priority Queue, Heap

В тази тема ще разгледаме абстрактната структура данни Приоритетна Опашка (Priority Queue) и конкретна нейна имплементация чрез Пирамида (Heap). Ще видим какви операции поддържа и с каква сложност се изпълнява всяка от тях. В края на темата сме предоставили и пълна имплементация чрез шаблонен клас, както и код, с който може да тествате ваша такава.

Автор: Александър Георгиев

Всъщност Priority Queue е само абстрактно понятие за структура данни, която поддържа тези операции. Heap е нейна специфична имплементация, която ще разгледаме в тази тема. Съществуват, обаче, и други възможни (ефективни) имплементации на Priority Queue - например Fibonacci Heap, Red-black Trees, и други.

В тази тема ще ви запознаем с абстрактната структура данни Приоритетна Опашка (Priority Queue), и нейната най-популярна реализация - Пирамида (Heap). Тя е сравнително лесна както за разбиране, така и за писане, като в същото време е много полезна поради ефективността на операциите си и многобройните си приложения в задачи от реалния живот.

Проблем

В рецепцията на реномиран хотел чакат да се регистрират голям брой посетители. Някои от тях са по-важни за хотела, тъй като биха донесли по-голяма печалба и/или популярност - например дипломати, влиятелни бизнесмени, известни актьори и т.н. След всеки обработен човек, рецепционистите трябва да избират кого да обработят следващ. Те искат винаги това да е най-важният все още ненастанен човек.
За тяхна зла участ, от време на време в хотела пристигат нови хора, които могат да са с произволна важност.

Абстракция

Имаме голям брой конкуриращи се обекти, всеки от които има даден приоритет (важност), с който трябва да го обработим. В процеса на работа могат да се появяват нови обекти със свой собствен приоритет (потенциално много нисък или много висок). От нас се иска да можем бързо да:

Добавяме нов обект с даден приоритет;
Намираме обекта с най-голям приоритет;
Премахваме обекта с най-голям приоритет.

Употреба

Поради ефективната си имплементация и често възникващите проблеми от реалния живот, които изискват приоритизиране на дадени операции, тази структура данни намира редица приложения. Тук сме изброили само някои от тях.

Намиране на най-къс път

Може би най-известното приложение на приоритетната опашка е като част от алгоритъма на Дейкстра за намиране на най-къс път в граф. В реалния живот той се ползва на много места - от това, как да стигнете от вкъщи до срещата с приятелите ви (maps), до това, как интернет трафикът ви да бъде рутиран до сървъра и обратно до вас. Без приоритетна опашка гледането на котки в YouTube би било далеч по-малко удоволствие.

Сортиране

Heapsort е един от най-популярните ефективни алгоритми за сортиране, тъй като е inplace (тоест му е нужна O(1) допълнителна памет), няма "лоши" случаи (както, например, Quicksort), а също така е и сравнително лесен за имплементация.

Процеси в Операционна Система

?	Тъй като броят процеси обикновено е сравнително малък, а също така приоритетът на даден процес с времето може да се променя, за избор на процес съществуват и други често-използвани техники.

Изборът на това на кой процес в операционната система да бъдат дадени ресурси (процесорно време) е именно задача, изискваща приоритетна опашка.

Бързи кодирания

Някои от най-често ползваните алгоритми за компресия на информация (например тези, базирани на Huffman Coding) се нуждаят от бързо намиране на двете най-малки стойности от дадено множество. Приоритетната опашка тук пасва чудесно, тъй като тя лесно може да бъде модифицирана да намира елементите с най-малък (вместо с най-голям) приоритет.

Heap

Най-честата имплементация на приоритетна опашка е чрез структурата данни Heap (пирамида). Тя е сравнително лесна за имплементация, като в същото време предоставя много ниска допълнителна константа при изпълняване на операциите. Като допълнителен бонус, тя заема минималната възможна O(N) памет и би могла да бъде имплементирана както в последователен блок памет, така и в отделни парчета.

При нея вкараните елементи се държат в (почти*) пълно двоично дърво, чиито корен съдържа максималния елемент. Децата на всеки връх от дървото (ако има такива) имат по-малък или равен приоритет от този на баща им. Това позволява лесно поддържане на структурата в този вид при добавяне или премахване на елемент от нея.

*Под "почти" пълно двоично дърво имаме предвид двоично дърво, в което всяко от нивата е изцяло запълнено, освен, потенциално, последното. При това, всички елементи на последното ниво са възможно най-"наляво".

Данни

В нашата имплементация ще ползваме един единствен блок памет (масив), който ще съдържа всички елементи на пирамидата. Разбира се, тъй като броят елементи може да се променя, за целта ще ползваме динамичен масив. В неговия нулев елемент ще държим корена на дървото, а децата на връх с индекс idx имат индекси idx * 2 + 1 и idx * 2 + 2. Обратно, лесно можем да намерим и бащата на всеки връх - неговият индекс би бил (idx - 1) / 2.

Максимален елемент

Взимането на максималния елемент от пирамидата е тривиално. Както казахме, ако тя съдържа поне един елемент, то коренът ѝ (елементът на позиция 0 в масива) ще е именно този максимален елемент.

typedef
 int
 DataType;

DataType top(vector
 <
DataType>
& heap) {
    return
 heap[0
];
}

Добавяне на елемент

Добавяме новия елемент като ново листо на дървото. Тъй като дървото е пълно или почти пълно двоично дърво, то това е еквивалентно да го сложим просто на позиция size в масива, където size е текущият брой елементи. Ако ползваме vector, това не е нищо повече от heap.push_back(newElement).

В този момент е възможно двоичното дърво да няма желаните свойства за пирамида (например, представете си, че сме добавили елемент с много висок приоритет, който трябва да отиде на върха). За да възвърнем тези му свойства, ще бутаме елемента нагоре в дървото, докато не се случи едно от следните две:

Елементът стане корен на дървото;

Текущият му баща е по-голям или равен на него.

Примерна имплементация на тази операция:

void
 push(vector
 <
DataType>
&
 heap, DataType value) {
    heap.push_back(value);
    pullUp(heap,
 (int
)heap.size() -
 1
);
}

void
 pullUp(vector
 <
DataType>
&
 heap,
 int index) {
    while
 (index >
 0) {
        int
 parent =
 (index -
 1
) >
>
 1
;
        if
 (heap[parent] < heap[index]) {
            swap(heap[parent],
 heap[index]);
            index =
 parent;
        }
        else
 break
;
    }
}

Ако в пирамидата е имало N елемента, следователно дървото ѝ има log(N) нива. Тъй като движим новия елемент единствено нагоре, то сложността на тази операция е O(logN).

Премахване на елемент

При приоритетната опашка обикновено единственият елемент, който бихме премахвали, е този с максимална стойност, тъй като той е единственият, за който знаем точната му наредба спрямо всички останали. Затова тук считаме, че ще премахваме само корена.

Ако пирамидата е съдържала само един елемент, просто го премахваме и нямаме какво друго да правим. В противен случай на място на корена слагаме последния елемент от вектора. Това е удобно, тъй като:

Премахването на последния елемент от вектор е бързо (O(1));

Така запазваме "вида" на дървото - то остава (почти) пълно двоично дърво.

Възможно е след това преместване дървото ни да няма желаните свойства за пирамида. Затова ще продължим да местим този елемент (бившият последен елемент на вектора) докато ги възвърнем. Тъй като елементът в момента се намира в корена, нямаме друг избор, освен да го местим надолу по дървото.

Това правим по следният алчен начин, който води до възвръщане на свойствата на пирамида:

Ако елементът няма деца (тоест е станал листо на дървото) или децата му са с по-малък или равен приоритет на неговия, спираме;
В противен случай го разменяме с по-голямото* от децата му и продължаваме да разглеждаме същия елемент спрямо новата му позиция (и нови деца).

*Ако трябва да разменим елемента с някое от децата му и те имат равни стойности, няма значение кое от двете ще изберем.

Примерна имплементация на тази операция:

void
 pop(vector
 <
DataType>
& heap) {
    heap[0
] =
 heap.back();
    heap.pop_back();
    pushDown(heap,
 0
);
}

void
 pushDown(vector
 <
DataType>
&
 heap,
 int index) {
    while
 ((index <
<
 1
) +
 1
 <
 (int)heap.size()) {
        int
 child =
 (index <
<
 1
) +
 1
;
        if
 (child +
 1
 <
 (int)heap.size())
            if
 (heap[child] <
 heap[child +
 1])
                child+
+
;
        if
 (heap[index] < heap[child]) {
            swap(heap[index],
 heap[child]);
            index =
 child;
        }
        else
 break
;
    }
}

Този път местим елемент единствено надолу в дърво с log(N) нива. Лесно можем да видим, че и тази операция е O(logN).

Създаване на пирамида от елементи

Интересно свойство на пирамидата е, че тя може бързо да бъде създадена от несортирано множество от елементи. С каква сложност бихте очаквали да става това? Интуицията подсказва O(N∙logN), но в действителност това е грешно - можем и по-бързо!

Ако просто сложим елементите във вектор и на всеки от тях (обхождайки ги в обратен ред) извършим pushDown, накрая векторът ще е пирамида.

Сравнително лесно се вижда защо накрая ще се получи пирамида, но не е толкова очевидно защо сложността на това нещо е O(N). Да, наистина, тя е линейна!

Всеки от елементите от последното ниво на дървото (N/2 на брой) не сме преместили - те нямат деца, следователно няма къде да ходят;
Всеки от елементите от предпоследното ниво на дървото (N/4 на брой) сме преместили максимум веднъж - ако имат деца, то те са със сигурност листа. Следователно, дори да се наложи да местим даден елемент, това ще е най-много веднъж;
Аналогично, всеки от елементите на пред-пред-последното ниво (N/8 на брой) можем да преместим най-много две нива надолу;

Елементите от второто ниво на дървото (2 на брой) сме преместили максимум log(N) - 2 пъти;
Елементите от първото ниво на дървото (1 на брой) сме преместили максимум log(N) - 1 пъти.

Сумирайки горните операции имаме (N / 2) * 0 + (N / 4) * 1 + (N / 8) * 2 + ... + 2 * (log(N) - 2) + 1 * (log(N) - 1), което е < N.

Добре, тогава не можем ли да сортираме N числа за O(N)? Все пак строенето е O(N), a взимането на максимума е O(1) o.O?

За съжаление - не. Което пропускаме е, че не просто трябва да вземем максимума, а трябва и да го премахнем след това за всеки един от N-те елемента - което вече е със сложност O(logN). Така сортирането с heap става O(N∙logN) -- колкото са и много от другите ефективни алгоритми за сортиране.

Сложности на Операциите

Тази имплементация на пирамида постига следните сложности:

O(1) за достъп до максималния елемент;
O(logN) за добавяне на елемент;
O(logN) за премахване на максималния елемент;
O(N) за строене от дадени N елемента.

STL Priority Queue

Приоритетна опашка е имплементирана в стандартната библиотека на C++. Тя се намира в хедъра <queue> и е от вида priority_queue<T>. За да демонстрираме употребата ѝ ще ползваме следния код, който чете N числа и печата нечетните от тях в намаляващ ред (малко глупав пример и имплементация, знам).

#include <cstdio>
#include <queue>
using
 namespace
 std;

int
 main(void) {
    int
 N;
    priority_queue
 <
int
>
 q;

    fscanf(stdin
,
 "%d"
,
 &
N);
    for
 (int
 i =
 0
;
 i <
 N;
 i+
+) {
        int
 val;
        fscanf(stdin
,
 "%d"
,
 &
val);
        q.push(val);
    }
    while
 (!q.empty()) {
        if
 (q.top() %
 2)
            fprintf(stdout
,
 "%d\n"
,
 q.top());
        q.pop();
    }
    return
 0
;
}

Min-Heap vs. Max-Heap

Ако ни трябва min-heap, но имаме имплементиран max-heap (например този, който е имплементиран в STL), то може да го ползваме без абсолютно никакви промени в кода му! Трик: вместо да вкарваме приоритетите, ще вкарваме техните отрицателни стойности (тоест приоритет X става -X). Лесно можете да видите, че 5 е повече от 2, но -2 е повече от -5.

Стандартната имплементация (тази, която писахме тук) предоставя бърз достъп до най-големия елемент в множеството (тоест този с най-голям приоритет). Този вид пирамида се нарича "Max-heap". В много задачи, обаче, не ни трябва най-големият, а най-малкият такъв (например за алгоритъма на Дейкстра). За щастие, това не променя почти нищо в имплементацията ни - просто трябва да заменим "<" с ">" (или обратно), навсякъде, където сравняваме елементи (или техните приоритети) в структурата.

Друг вариант е да "предефинираме" operator < за дадените елементи. Това е особено лесно, ако елементите в heap-а са дефинирана от нас структура или клас.

Трети вариант е (ако ползваме STL-ската приоритетна опашка) да подадем удачна функция (по-точно клас) за сравнение. По подразбиране, тя е дефинирана да работи със стандартната наредба на елементите (тоест за "по-малко" се ползва вграденият клас less, който прави точно това, което очаквате). Вместо това, можете да подадете като трети аргумент неговата противоположност greater:

priority_queue
 <
 int
,
 vector
 <
int
>
,
 greater<
int
>
 >
 q;

Тук първият аргумент е от какъв тип ще са стойностите в приоритетната опашка, вторият е в какъв контейнер да се пазят (по подразбиране vector и никога в състезателния ми опит не се е налагало да ползвам нещо друго), а третият е класът за сравнение. Забележете, че самите вие можете да напишете този клас и да го подадете като аргумент. Например, ето приоритетна опашка, която сортира студенти по точки (в намаляващ ред), а при равни точки - по име (в нарастващ ред).

#include <cstdio>
#include <queue>
#include <string>
using
 namespace
 std;

struct Student {
    string
 name;
    int
 score;
    Student(string
 name_ =
 ""
,
 int
 score_ =
 0
) :
    name(name_), score(score_) {}
};

class StudentComparer {
    public
:
    bool
 operator
() (const
 Student&
 lhs,
 const
 Student&
 rhs) const {
        return
 lhs.score !
=
 rhs.score ?
 lhs.score <
 rhs.score :
        lhs.name >
 rhs.name;
    }
};

int
 main(void) {
    priority_queue
 <
Student,
 vector
 <
Student>
,
 StudentComparer>
 q;
    q.push(Student("Elly"
,
 100
));
    q.push(Student("Aia"
,
 87
));
    q.push(Student("Stancho"
,
 100
));
    while
 (!q.empty()) {
        fprintf(stdout
,
 "%s with score %d.\n"
,
        q.top().name.c_str(),
 q.top().score);
        q.pop();
    }
    // Prints Elly, then Stancho, then Aia.
};

Разбира се, в случая далеч по-просто би било да предефинираме operator < в нашата структура, но ако, например, трябваше да имаме една приоритетна опашка, която пази най-големите, и една, която пази най-малките (както, например, трябва да направим в задачата Medians), това би било невъзможно.

Примерни Задачи

Решете задачата Medians.

Пълна Имплементация

Сравнително хубава цялостна имплементация и тестове: Heap.h | HeapTester.cpp

Допълнителна информация

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 10226 пъти.