Cues de Prioritat i Arbres Generals

Part I. Cues de Prioritat

Una cua de prioritat és una cua a on cada element té una prioritat

Una cua de prioritat és un contenidor semblant a una cua normal, però amb una diferència fonamental: quan extraiem un element amb pop, sempre surt l'element amb la prioritat més alta (el valor més gran). No es respecta l'ordre d'arribada com en una cua FIFO, sinó que l'element amb el valor més gran sempre és el proper en sortir.

Si intentem implementar una cua de prioritat directament amb un vector, tenim dues opcions:

1. Inserció ordenada: mantenim el vector ordenat. El push és $O(n)$ (hem de trobar la posició correcta i moure elements), però el pop és $O(1)$ (eliminem l'últim element).

2. Inserció desordenada: posem l'element al final. El push és $O(1)$, però el pop és $$ (hem de buscar el màxim).

Cap de les dues opcions és del tot eficient. Per aconseguir $O(\log n)$ tant per inserció com per extracció, necessitem una estructura especial: el binary heap.

Un binary heap és un arbre complet emmagatzemat en un vector

Un binary heap és un arbre binari complet (tots els nivells estan plens excepte possiblement l'últim, que s'omple d'esquerra a dreta) que s'emmagatzema directament en un vector. Cada nivell de l'arbre ocupa un rang continu de posicions al vector.

Per a un heap amb $N$ nodes, l'alçada és $O(\log N)$, cosa que garanteix que les operacions de pujar i baixar per l'arbre siguin eficients.

Hi ha dos tipus de binary heap:

• Max heap: el valor de cada node és major o igual que el dels seus fills. L'element màxim és l'arrel.
• Min heap: el valor de cada node és menor o igual que el dels seus fills. L'element mínim és l'arrel.

A PRO2 implementarem un max heap.

La relació d'índexs entre pare i fills és un càlcul molt simple

L'arbre s'emmagatzema al vector començant per la posició 1 (la posició 0 no s'utilitza). Amb aquesta convenció, per a un node a la posició $i$:

Per exemple, l'arrel està a la posició 1. Els seus fills estan a les posicions 2 i 3. Els fills del node 2 estan a les posicions 4 i 5, i els fills del node 3 estan a les posicions 6 i 7.

Propietat del heap: cada node és major o igual que els seus fills

La propietat del heap (en un max heap) és que per a cada node, el seu valor és major o igual que el valor dels seus fills. Això implica que el valor màxim de tot el heap és sempre l'arrel, a la posició 1 del vector.

Totes les operacions del heap es basen en mantenir aquesta propietat.

Hi ha tres operacions principals: top, push i pop

Les tres operacions fonamentals d'un heap són:

• top: obtenir l'element màxim (l'arrel).
• push: inserir un nou element al heap.
• pop: extreure l'element màxim (l'arrel).

Les tres operacions han de preservar la propietat del heap després de modificar l'estructura.

top: obtenir l'element màxim (l'arrel)

Per obtenir l'element màxim:

1. Es retorna l'element a la posició 1 (l'arrel).

Aquesta operació es diu top:

template <typename T>
const T& Heap<T>::top() const {
    assert(!empty(), "top: referència a un element inexistent, heap buit");
    return elems_[1];
}

push: insertar, intercanviar i pujar fins que es pugui

Per inserir un element:

1. Es col·loca el nou element al final del vector (a la primera posició lliure, que és la posició size).
2. L'element pot ser més gran que el seu pare, violant la propietat del heap. Per arreglar-ho, es compara amb el pare i, si és més gran, s'intercanvien.
3. Es repeteix el procés pujant fins que l'element trobi un pare més gran o arribi a l'arrel.

Aquesta operació es diu flow up:

template <typename T>
void Heap<T>::flow_up_(int i) {
    while (i > 1 && elems_[i] > elems_[i / 2]) {
        std::swap(elems_[i], elems_[i / 2]);
        i /= 2;
    }
}

El push simplement afegeix l'element i crida flow_up_:

void push(const T& x) {
    resize_(1);
    elems_[size_] = x;
    flow_up_(size_);
}

pop: extreure, moure l'últim al principi, i baixar fins que es pugui

Per extreure l'element màxim:

1. Es copia l'últim element del vector a la posició 1 (l'arrel), sobreescrivint el màxim.
2. Es redueix la mida del heap.
3. L'element mogut a l'arrel pot ser més petit que algun dels seus fills, violant la propietat. Per arreglar-ho, es compara amb els dos fills i s'intercanvia amb el fill més gran (cal escollir la branca correcta a la baixada!).
4. Es repeteix el procés baixant fins que l'element trobi fills més petits o arribi a una fulla.

Aquesta operació es diu flow down:

template <typename T>
void Heap<T>::flow_down_(int i) {
    int left = 2 * i, right = 2 * i + 1;
    int max = i;
    if (left <= size_ && elems_[left] > elems_[max]) {
        max = left;
    }
    if (right <= size_ && elems_[right] > elems_[max]) {
        max = right;
    }
    if (max != i) {
        std::swap(elems_[i], elems_[max]);
        flow_down_(max);
    }
}

El pop fa el moviment i crida flow_down_:

void pop() {
    assert(!empty(), "pop: heap buit");
    elems_[1] = elems_[size_];
    resize_(-1);
    flow_down_(1);
}

Cost de les operacions: $O(1)$ per top, $O(\log n)$ per push i pop

Com que l'arbre és complet i té alçada $O(\log n)$, les operacions de pujar i baixar fan com a màxim $O(\log n)$ intercanvis. Resumint:

Això és molt millor que les dues opcions amb vector directe, on una de les operacions era $O(n)$.

Ús d'un Heap<Elem> quan l'element és una tupla

El heap compara els elements amb l'operador >. Si el tipus dels elements és una tupla (o una classe), cal definir l'operador de comparació. Un operador en C++ es pot redefinir implementant una funció amb el nom operator OP, on OP és l'operador que volem redefinir.

Per exemple, si volem una cua de prioritat de persones amb un nom i una prioritat:

struct Persona {
    string nom;
    int prioritat;
};

bool operator>(const Persona& a, const Persona& b) {
    return a.prioritat > b.prioritat;
}

La funció operator> s'assembla molt a la que feiem servir a PRO1 per ordenar vectors, malgrat ara tingui aquest nom tan curiós, i el fet que a PRO1 implementava si a era menor que b.

Amb això, podem declarar un Heap<Persona> i el heap organitzarà les persones per la seva prioritat:

#include "heap.hh"
using namespace pro2;

int main() {
    Heap<Persona> cua;
    cua.push({"Anna", 3});
    cua.push({"Carla", 1});
    cua.push({"Berta", 7});

    while (!cua.empty()) {
        cout << cua.top().nom << " (prioritat " << cua.top().prioritat << ")" << endl;
        cua.pop();
    }
}
// Sortida:
// Berta (prioritat 7)
// Anna (prioritat 3)
// Carla (prioritat 1)

Implementació completa del Heap<T>

La implementació del Heap<T> a PRO2 fa servir un vector intern amb la posició 0 sense usar, i mètodes privats per pujar i baixar elements:

#ifndef HEAP_HH
#define HEAP_HH

#include <vector>
#include "assert.hh"

namespace pro2 {

template <typename T>
class Heap {
    std::vector<T> elems_;
    int size_;

    void resize_(int d);
    void flow_down_(int i);
    void flow_up_(int i);

 public:
    Heap() : size_(0), elems_(1) {}

    int size() const { return size_; }
    bool empty() const { return size_ == 0; }

    const T& top() const {
        assert(!empty(), "top: heap buit");
        return elems_[1];
    }

    void push(const T& x) {
        resize_(1);
        elems_[size_] = x;
        (size_);
    }

    {
        (!(), );
        elems_[] = elems_[size_];
        ();
        ();
    }
};

 < T>
 Heap<T>::( d) {
     new_size = size_ + d;
     (new_size > elems_.() - ) {
        elems_.(elems_.() * );
    }   (new_size < elems_.() / ) {
        elems_.(elems_.() / );
    }
    size_ = new_size;
}

 < T>
 Heap<T>::( i) {
     left =  * i, right =  * i + ;
     max = i;
     (left <= size_ && elems_[left] > elems_[max]) {
        max = left;
    }
     (right <= size_ && elems_[right] > elems_[max]) {
        max = right;
    }
     (max != i) {
        std::(elems_[i], elems_[max]);
        (max);
    }
}

 < T>
 Heap<T>::( i) {
     (i >  && elems_[i] > elems_[i / ]) {
        std::(elems_[i], elems_[i / ]);
        i /= ;
    }
}

}  

Part II. Arbres Generals

Un arbre general té un nombre arbitrari de fills

Recordem que un arbre binari té exactament dos fills (esquerre i dret), que poden ser buits. Una generalització de l'arbre binari és un arbre general, que té un nombre variable de fills. La classe Tree<T> modela això: cada node té un valor i una col·lecció de subarbres (un vector de Tree<T>).

La diferència principal amb BinTree<T> és que aquí no hi ha "fill esquerre" i "fill dret", sinó un conjunt de fills indexats: s'accedeix al fill $i$-èsim amb child(i), i es consulta el nombre de fills amb num_children().

Declaració de la classe Tree<T>

La interfície de Tree<T> és la següent:

Constructors:

• Tree() — construeix un arbre buit.
• Tree(const Tree& other) — construeix una còpia d'un altre arbre.
• Tree(const T& value) — construeix un arbre amb un sol node (valor value) i sense fills, és a dir, una fulla.
• Tree(const T& value, const vector<Tree>& children) — construeix un arbre amb arrel value i els fills donats al vector.

Consultes:

Per a qualsevol Tree<T>:

• empty() — retorna true si l'arbre és buit, false en cas contrari. És l'única operació que sempre es pot cridar.

Només si l'arbre no és buit:

• value() — retorna el valor de l'arrel.
• num_children() — retorna el nombre de fills.
• child(i) — retorna el fill $i$-èsim. Cal que $0 \le i <$ num_children().

Com amb BinTree<T>, no hi ha mètodes per modificar un arbre existent; les operacions que "canvien" l'arbre construeixen un nou Tree.

Exemple de creació amb tots els constructors i accés als fills

#include <iostream>
using namespace std;

#include "tree.hh"
#include "tree-io.hh"
using namespace pro2;

int main() {
    Tree<int> t1;     // buit
    Tree<int> t2(1);  // una fulla amb valor 1
    Tree<int> t3(2, { t1, t2, Tree<int>(-3), Tree<int>(0) });

    cout << t3.value() << endl;             // 2
    cout << t3.num_children() << endl;      // 4
    cout << t3.child(0).empty() << endl;    // true (t1 és buit)
    cout << t3.child(1).value() << endl;    // 1
    cout << t3.child(2).value() << endl;    // -3
    cout << t3.child(3).value() << endl;    // 0
}

Un exemple més il·lustratiu amb un arbre que representa un disc dur:

// clang-format off
Tree<string> disk("C:", {
    Tree<string>("Windows", {
        Tree<string>("System32")
    }),
    Tree<string>("Program Files", {
        Tree<string>("Adobe"),
        Tree<string>("Microsoft")
    }),
    Tree<string>("Users", {
        Tree<string>("Groucho"),
        Tree<string>("Chicco"),
        Tree<string>("Harpo")
    }),
});
// clang-format on

Funcions anàlogues als arbres binaris

En arbres generals, els recorreguts es fan iterant sobre els fills (de 0 a num_children()-1) i cridant recursivament la funció sobre cada child(i). L'esquema general és molt similar al dels arbres binaris, però en comptes de fer dues crides recursives (una per cada fill), fem un bucle.

Alçada d'un arbre general

L'alçada d'un arbre general es defineix com en els arbres binaris: un arbre buit té alçada 0; un arbre no buit té alçada 1 més el màxim de les alçades dels fills. La diferència és que ara iterem sobre tots els fills:

int tree_height(Tree<int> t) {
    if (t.empty()) {
        return 0;
    }
    int hmax = 0;
    for (int i = 0; i < t.num_children(); ++i) {
        hmax = max(hmax, tree_height(t.child(i)));
    }
    return 1 + hmax;
}

Cerca d'un valor en un arbre general

Comprovar si un valor x apareix en l'arbre: si l'arbre és buit, no hi és; si el valor de l'arrel coincideix amb x, hi és; si no, es busca en cadascun dels fills, aturant-se tan bon punt es trobi:

bool tree_search(Tree<int> t, int x) {
    if (t.empty()) {
        return false;
    }
    if (t.value() == x) {
        return true;
    }
    for (int i = 0; i < t.num_children(); i++) {
        if (tree_search(t.child(i), x)) {
            return true;
        }
    }
    return false;
}

Aquí el curtcircuit no és amb || com en arbres binaris, sinó amb un return true dins del bucle, que atura la cerca en trobar el valor.

Número de nodes d'un arbre general

Per comptar tots els nodes d'un arbre, sumem 1 (per l'arrel) al nombre de nodes de tots els fills:

int num_nodes(Tree<int> t) {
    if (t.empty()) {
        return 0;
    }
    int count = 1;
    for (int i = 0; i < t.num_children(); i++) {
        count += num_nodes(t.child(i));
    }
    return count;
}

Sumar 1 a tots els nodes

Construïm un nou arbre amb la mateixa estructura però amb cada valor incrementat en 1. Cal construir recursivament els fills transformats i posar-los en un vector per crear el nou node:

Tree<int> add_one(Tree<int> t) {
    if (t.empty()) {
        return Tree<int>();
    }
    vector<Tree<int>> new_children;
    for (int i = 0; i < t.num_children(); i++) {
        new_children.push_back(add_one(t.child(i)));
    }
    return Tree<int>(t.value() + 1, new_children);
}

Codi de Heap<T> i Tree<T>