Binary Heap
V této části si ukážeme Binary Heap. Tato datová struktura patří do Tree kategorie jménem Heap. Je to jen další druh stromové datové struktury. Co všechno za datové struktury v kategorii Heap existuje si můžete prohlédnout v tomto seznamu.
Co je to Binary Heap
Binary Heap je datová struktura podobná Binary Search Tree. Narozdíl od něj má ale trochu jiná pravidla. Binary Heap se rozděluje na dva typy: Max Binary Heap a Min Binary Heap. V Max Binary Heap mají potomci menší hodnotu než jejich předci, a v Min Binary Heap mají potomci větší hodnotu než jejich předci. V Binary Heap mezi potomky neexistují žádné podmínky jako tomu je u Binary Search Tree. Všechny node uchovávají tolik potomků, kolik jen mohou a nejdříve se zaplňují potomci nalevo. Než se začnou přidávat potomci na další úroveň, tak se nejdříve musí zaplnit stávající. Co přesně tím myslím potom uvidíte v ukázce.
Binary Heap se používá pro implementování Priority Queue, což je velmi často používaná datová struktura. Také se používá pro algoritmy sloužící pro procházení graphů.
Jakým způsobem jsou v Binary Heap uložená data
U Binary Search Tree jsme hodnoty ukládali v objektech, vytvořených pomocí třídy Node. U Binary Heap bychom to tak mohli také udělat, ale máme lepší možnost. K ukládání hodnot v Binary Heap můžeme použít pole.
Pokud budeme hodnoty v Binary Heap ukládat pomocí pole, tak v tom musíme mít nějaký systém. Hodnoty musí být v poli uložené v nějakém logickém pořadí. Také musíme mít nějaký způsob, jak v poli pro jednotlivé hodnoty budeme získávat potomky a předky.
Hodnoty jsou v poli seřazené tímto způsobem: první hodnota v poli je root a další dvě hodnoty v poli jsou její potomci. Pro druhou hodnotu v poli (na indexu 1) jsou potomci na indexu 3 a 4, pro třetí hodnotu v poli (na indexu 2) jsou potomci na indexu 5 a 6, a tak to stále pokračuje. Následující ukázka to vizuálně ukazuje.
Pro každou hodnotu v poli musíme být schopni získat její potomky a předka. Budeme to potřebovat v metodách, až si Binary Heap zkusíme vytvořit. Existují k tomu tyto vzorce (n představuje index hodnoty, pro kterou vzorec používáme):
- získání prvního (levého) potomka: 2n+1
- získání druhého (pravého) potomka: 2n+2
- získání předka: (n-1)/2 (bez desetinné části, chceme index)
Vytvoření základu Max Binary Heap
Binary Heap může být typu Max nebo Min. V tomto tutoriálu si zkusíme vytvořit Max Binary Heap. Každý potomek tedy bude obsahovat menší hodnotu než jeho předek. Pokud víme jak vytvořit Max Binary Heap, tak je jednoduché předělat jej na Min Binary Heap, proto si teď zkusíme vytvořit jen jeden typ.
Pro Max Binary Heap si vytvoříme třídu, která bude obsahovat pole, do kterého si později budeme ukládat hodnoty. Nic víc nepotřebujeme, později si do ní přidáme metody.
// třída pro Max Binary Heap
class MaxBinaryHeap {
constructor() {
this.values = [];
}
}Metoda insert
Pro přidání hodnoty do Binary Heap si vytvoříme metodu insert. Tato metoda přidá hodnotu na konec pole a zavolá metodu bubbleUp, která se postará o to, aby se naposledy vložená hodnota umístila v poli na správné místo. U Max Binary Heap platí, že potomci mají vždy menší hodnotu než jejich předek. Metoda bubbleUp tedy zajišťuje, že to tak bude i po vložení hodnoty na konec pole.
class MaxBinaryHeap {
/* ... */
// metoda pro přidání hodnoty do Binary Heap
insert(element) {
// hodnota se vloží na konec pole values
this.values.push(element);
// zavolání metody bubbleUp, která umístí naposledy vloženou hodnotu na správné místo (aby byl předek vždy větší než jeho potomci)
this.bubbleUp();
}
// tato metoda umístí naposledy vloženou hodnotu na správné místo (aby byl předek vždy větší než jeho potomci)
bubbleUp() {
// získání indexu poslední položky v poli
let idx = this.values.length-1;
// tento cyklus bude probíhat tak dlouho, dokud bude index idx větší než 0
while (idx > 0) {
// získání indexu předka, hodnoty na indexu idx
const parentIdx = Math.trunc((idx-1)/2);
// pokud je hodnota na indexu idx menší než její předek, tak se hodnota zařadila na správné místo a cyklus může skončit
if (this.values[idx] <= this.values[parentIdx]) break;
// vyměnění hodnoty mezi indexy parentIdx a idx
const parent = this.values[parentIdx];
this.values[parentIdx] = this.values[idx];
this.values[idx] = parent;
// změnění indexu idx na předka hodnoty, na kterou momentálně index idx ukazuje
idx = parentIdx;
}
}
}
// vytvoření Max Binary Heap
const heap = new MaxBinaryHeap();
// vložení hodnot do Max Binary Heap
heap.insert(39);
heap.insert(41);
heap.insert(33);
heap.insert(52);
heap.insert(15);
heap.insert(43);
heap.insert(55);Metoda extractMax
Jako druhou metodu si pro naši MaxBinaryHeap třídu vytvoříme metodu extractMax. Tato metoda bude sloužit k odstranění a získání root hodnoty z Binary Heap.
Metoda extractMax odstraní z pole values poslední položku a její hodnotu nastaví první položce pole. Po této operaci se zavolá metoda sinkDown, která zajistí, že se první (root) hodnota pole přemístí na takové místo, aby potomci v Binary Heap měli vždy menší hodnotu než jejich předek.
class MaxBinaryHeap {
/* ... */
// metoda pro odstranění a získání root hodnoty z Binary Heap
extractMax() {
// uložení první (root) hodnoty z pole values do proměnné max
const max = this.values[0];
// získání a odstranění poslední hodnoty z pole values
const end = this.values.pop();
// pokud pole values není prázdné, tak se první (root) položka pole nastaví na hodnotu odstraněné položky
if (this.values.length > 0) {
this.values[0] = end;
// zavolání metody sinkDown, která přemístí novou root hodnotu na správné místo v poli
this.sinkDown();
}
// vrácení odstraněné hodnoty
return max;
}
// tato metoda přemístí první (root) hodnotu v poli values na správné místo (aby byl předek vždy větší než jeho potomci)
sinkDown() {
// proměnná idx bude uchovávat index přemisťované hodnoty (první (root) položky pole values)
let idx = 0;
// získání délky pole values
const length = this.values.length;
// uložení hodnoty první (root) položky pole values
const element = this.values[0];
// tento cyklus bude probíhat tak dlouho, dokud se první hodnota v poli values nepřemístí na takové místo, aby byl v Binary Heap předek vždy větší než jeho potomci
while (true) {
// získání indexů potomků přemisťované hodnoty
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
// do těchto proměnných se později uloží hodnoty potomků
let leftChild, rightChild;
// tato proměnná bude později určovat index potomka přemisťované hodnoty, se kterým se bude vyměňovat
let swap = null;
// pokud má přemisťovaná hodnota prvního (levého) potomka
if (leftChildIdx < length) {
// uložení hodnoty prvního (levého) potomka
leftChild = this.values[leftChildIdx];
// pokud je potomek větší než předek (přemisťovaná hodnota), tak se proměnná swap nastaví na jeho index
if (leftChild > element) {
swap = leftChildIdx;
}
}
// pokud má přemisťovaná hodnota druhého (pravého) potomka
if (rightChildIdx < length) {
// uložení hodnoty pravého potomka
rightChild = this.values[rightChildIdx];
// pokud je pravý potomek větší než předek a levý potomek, tak se proměnná swap nastaví na jeho index
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
// pokud se přemisťovaná hodnota nemá měnit se svým potomkem, tak se hodnota umístila na správné místo a cyklus může skončit
if (swap === null) break;
// prohození přemisťované hodnoty s jejím potomkem
this.values[idx] = this.values[swap];
this.values[swap] = element;
// index idx již neukazuje na přemisťovanou hodnotu, tento kód to napraví
idx = swap;
}
}
}
// vytvoření Max Binary Heap
const heap = new MaxBinaryHeap();
// vložení hodnot do Max Binary Heap
heap.insert(39);
heap.insert(41);
heap.insert(33);
heap.insert(52);
heap.insert(15);
heap.insert(43);
heap.insert(55);
// odstranění první (root) hodnoty z Max Binary Heap
heap.extractMax();
heap.extractMax();
heap.extractMax();Více metod si již do naší MaxBinaryHeap třídy přidávat nebudeme. Ty hlavní jsme si ukázali a snad jste díky nim pochopili, jak Binary Heap funguje. Pokud byste potřebovali nějaké další, tak si myslím že byste si je asi zvládli vytvořit sami. Teď si ukážeme, jak můžeme Binary Heap použít pro implementování Priority Queue.
Priority Queue
Binary Heap se často používá pro vytvoření Priority Queue. Jde o datovou strukturu, ve které má každá položka nějakou prioritu. Priority Queue se podobá Queue, kterou jsme si ukazovali v části Stack a Queue. Rozdíl je v tom, že v Priority Queue mají položky přiřazenou prioritu a podle toho se uvnitř Priority Queue zařazují.
Priority Queue si můžeme například představit jako frontu lidí na nějaké pohotovosti v nemocnici. Pokud jako první přijde pacient s horečkou a jako druhý přijde pacient s postřelenou rukou, tak pacient s postřelenou rukou dostane vyšší prioritu a dostane se na řadu dříve.
Vytvoření základu Priority Queue
Pro Priority Queue si vytvoříme třídu, která bude stejně jako naše třída pro Max Binary Heap, obsahovat jen pole values, do kterého se budou ukládat položky. Později si do ní přidáme metodu enqueue pro přidání položky a metodu dequeue pro odstranění a získání položky. Namísto hodnot se budou v Priority Queue do pole values ukládat nodes. Takže si pro ně musíme také vytvořit třídu. Node bude obsahovat uchovávanou hodnotu a také prioritu, která bude určovat, kdy se položka dostane na řadu.
// třída pro node
class Node {
constructor(value, priority) {
this.value = value;
this.priority = priority;
}
}
// třída pro Priority Queue
class PriorityQueue {
constructor() {
this.values = [];
}
}Metoda enqueue
Pro přidání položky do Priority Queue si vytvoříme metodu enqueue. Bude stejná jako metoda insert, kterou jsme si vytvořili pro Max Binary Heap. Narozdíl od něj se ale do pole values bude ukládat nová node.
Metoda bubbleUp bude také skoro stejná jako metoda bubbleUp, kterou jsme si vytvořili pro Max Binary Heap. Jediný rozdíl bude v tom, že se bude porovnávat priorita položek namísto jejich hodnot.
class PriorityQueue {
/* ... */
// metoda pro přidání položky do Priority Queue
enqueue(value, priority) {
// přidání nové node na konec pole values
this.values.push(new Node(value, priority));
// zavolání metody bubbleUp, která umístí naposledy vloženou node na správné místo (aby měl předek vždy větší prioritu než jeho potomci)
this.bubbleUp();
}
// tato metoda umístí naposledy vloženou hodnotu na správné místo (aby měl předek vždy větší prioritu než jeho potomci)
bubbleUp() {
let idx = this.values.length-1;
while (idx > 0) {
const parentIdx = Math.trunc((idx-1)/2);
// v Priority Queue porovnáváme priority položek, jejich hodnoty ne
if (this.values[idx].priority <= this.values[parentIdx].priority) break;
const parent = this.values[parentIdx];
this.values[parentIdx] = this.values[idx];
this.values[idx] = parent;
idx = parentIdx;
}
}
}
// vytvoření Priority Queue
const queue = new PriorityQueue();
// vložení položek do Priority Queue
queue.enqueue(45, 3);
queue.enqueue(23, 4);
queue.enqueue(33, 2);
queue.enqueue(46, 6);
queue.enqueue(18, 2);
queue.enqueue(14, 7);
queue.enqueue(22, 1);Metoda dequeue
Pro odstranění a získání položky z PriorityQueue si vytvoříme metodu dequeue. Bude stejná jako metoda extractMax, kterou jsme si vytvořili pro Max Binary Heap. Rozdíl bude jen v metodě sinkDown, kterou metoda dequeue volá. Narozdíl od hodnot položek v poli values se bude porovnávat jejich priorita.
class PriorityQueue {
/* ... */
// metoda pro odstranění a získání položky z Priority Queue
dequeue() {
const max = this.values[0];
const end = this.values.pop();
if (this.values.length > 0) {
this.values[0] = end;
this.sinkDown();
}
return max;
}
// tato metoda přemístí první (root) hodnotu v poli values na správné místo
// (aby měli potomci v Priority Queue menší prioritu než jejich předek)
sinkDown() {
let idx = 0;
const length = this.values.length;
const element = this.values[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.values[leftChildIdx];
// v Priority Queue porovnáváme priority, hodnoty ne
if (leftChild.priority > element.priority) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.values[rightChildIdx];
// v Priority Queue porovnáváme priority, hodnoty ne
if (
(swap === null && rightChild.priority > element.priority) ||
(swap !== null && rightChild.priority > leftChild.priority)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.values[idx] = this.values[swap];
this.values[swap] = element;
idx = swap;
}
}
}
// vytvoření Priority Queue
const queue = new PriorityQueue();
// vložení položek do Priority Queue
queue.enqueue(45, 3);
queue.enqueue(23, 4);
queue.enqueue(33, 2);
queue.enqueue(46, 6);
queue.enqueue(18, 2);
queue.enqueue(14, 7);
queue.enqueue(22, 1);
// získání položek z Priority Queue
const polozka1 = queue.dequeue();
const položka2 = queue.dequeue();
const polozka3 = queue.dequeue();
Je tu jedna věc, na kterou bych vás měl upozornit. Pokud mají dvě položky v Priority Queue stejnou prioritu, tak není zaručené, že položku, kterou jsme do Priority Queue přidali jako první, také získáme jako první. Pokud bychom to chtěli napravit, tak bychom kromě priority mohli do node ukládat také například čas, kdy jsme položku do Priority Queue vložili. Tento čas bychom potom porovnávali společně s prioritami. Záleží na nás podle čeho chceme položky porovnávat. Můžeme mít klidně více kritérií, záleží na co konkrétně chceme Priority Queue použít.
Big O náročnost Binary Heap
Na závěr si ukážeme časovou náročnost některých operací s Binary Heap.
- přidávání položek: O(log n)
- odstraňování položek: O(log n)
- hledání položek: O(n)