Python - Heaps

Heap è una struttura ad albero speciale in cui ogni nodo padre è minore o uguale al suo nodo figlio. Quindi si chiama Min Heap. Se ogni nodo padre è maggiore o uguale al proprio nodo figlio, viene chiamato heap max. È molto utile implementare code di priorità in cui l'elemento della coda con un peso maggiore riceve maggiore priorità nell'elaborazione. Una discussione dettagliata sugli heap è disponibile nel nostro sito Web qui. Si prega di studiarlo prima se si è nuovi alla struttura dei dati principali. In questo capitolo vedremo l'implementazione della struttura dei dati dell'heap usando python.

Crea un mucchio

Un heap viene creato utilizzando la libreria incorporata di python denominata heapq. Questa libreria ha le funzioni rilevanti per eseguire varie operazioni sulla struttura dei dati dell'heap. Di seguito è riportato un elenco di queste funzioni.

• heapify: questa funzione converte un elenco normale in un heap. Nell'heap risultante l'elemento più piccolo viene spostato nella posizione di indice 0. Ma il resto degli elementi di dati non è necessariamente ordinato.
• heappush: questa funzione aggiunge un elemento all'heap senza alterare l'heap corrente.
• heappop: questa funzione restituisce l'elemento di dati più piccolo dall'heap.
• heapreplace - Questa funzione sostituisce l'elemento di dati più piccolo con un nuovo valore fornito nella funzione.

Creazione di un mucchio

Un heap viene creato semplicemente utilizzando un elenco di elementi con la funzione heapify. Nell'esempio seguente forniamo un elenco di elementi e la funzione heapify riorganizza gli elementi portando l'elemento più piccolo alla prima posizione.

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Quando il codice sopra viene eseguito, produce il seguente risultato:

[1, 3, 5, 78, 21, 45]

Inserimento in heap

L'inserimento di un elemento dati in un heap aggiunge sempre l'elemento all'ultimo indice. Ma puoi applicare di nuovo la funzione heapify per portare l'elemento appena aggiunto al primo indice solo se ha il valore più piccolo. Nell'esempio sotto inseriamo il numero 8.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

Quando il codice sopra viene eseguito, produce il seguente risultato:

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Rimozione dall'heap

È possibile rimuovere l'elemento al primo indice utilizzando questa funzione. Nell'esempio seguente la funzione rimuoverà sempre l'elemento nella posizione di indice 1.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Quando il codice sopra viene eseguito, produce il seguente risultato:

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Sostituzione in un mucchio

La funzione heapreplace rimuove sempre l'elemento più piccolo dell'heap e inserisce il nuovo elemento in entrata in un punto non fissato da alcun ordine.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]