2023-10-10 - heap

universityin-classsubject-2101

2023-10-10

Algoritmi

Heap (Priority Queue):

• Insert(k) con k priorità
• Max()
• Extract-Max()
• Delete(x) con x elemento
• Increase-Key(x, k) con x elemento e k priorità

la stessa struttura esiste anche al contrario (dove i valori più piccoli hanno priorità)

Tutti i metodi hanno complessità , tranne Max() che ha complessità .

A differenza dell’albero binario classico, l’heap è un albero binario (quasi) completo: tutti i livelli sono completi (ovvero sono presenti tutti i nodi) ad eccezione dell’ultimo che può non contenere degli elementi. Se però mancano degli elementi, allora quelli presenti sono allineati a sinistra.

Nel Max-Heap, ogni nodo ha la priorità più alta dei nodi figli.

In un albero completo, il numero di foglie è del numero di nodi interni. Il numero di foglie di un albero completo è uguale a dove è l’altezza dell’albero.

Heapify(x): crea un heap a partire dal nodo x. È utile quando non si è sicuri che l’heap a partire da x sia valido, nonostante i due figli lo siano (se non lo sono, l’algoritmo non funziona).
Si scambiano le chiavi del nodo x con quella del nodo figlio con chiave maggiore. Si richiama l’heapify ricorsivamente sul nodo figlio.

// O(log n)
void heapify(Node* x) {
	Node* left = node->left;
	Node* right = node->right;
	Node* max = x;
	if (left != nullptr && left->key > max->key)
		max = left;
	if (right != nullptr && right->key > max->key)
		max = right;
	if (max != x) {
		swap(x->key, max->key):
		heapify(max);
	}
}

Nell’heap è presente un puntatore detto HeapSize che punta al nodo più a destra dell’ultimo livello

void extractMax() {
	swap(root->key, heapSize->key);
	removeHeapSize(); // viene staccato il nodo puntato dall'heapSize dall'albero e viene aggiornato l'heapSize.
	heapify(root);
}

L’HeapSize viene approfondito nelle sezioni successive

void increaseKey(Node* x, Priority k) {
	x->key = k;
	while (x != root && x->parent->key < x->key) {
		swap(x->key, x->parent->key);
		x = x->parent;
	}
}

void insert(Priority k) {
	// aggiunge un nodo in corrispondenza dell'heapsize, incrementandolo
	Node* x = createNodeAtHeapSize(-INFINITY); // pseudocodice -infinito
	increaseKey(x, k);
}

void delete(Node *x) {
	swap(x->key, heapSize->key);
	removeHeapSize();
	heapify(x);
}

In realtà l’heap non viene implementato mediante un albero, bensì utilizzando un array.