Python - Heaps

Heap é uma estrutura de árvore especial na qual cada nó pai é menor ou igual a seu nó filho. Em seguida, é chamado de Min Heap. Se cada nó pai for maior ou igual a seu nó filho, ele será chamado de heap máximo. É muito útil implementar filas de prioridade onde o item da fila com maior peso recebe mais prioridade no processamento. Uma discussão detalhada sobre heaps está disponível em nosso site aqui. Por favor, estude-o primeiro se você for novo na estrutura de dados principal. Neste capítulo, veremos a implementação da estrutura de dados heap usando python.

Crie um Heap

Um heap é criado usando a biblioteca embutida do python chamada heapq. Esta biblioteca possui as funções relevantes para realizar várias operações na estrutura de dados heap. Abaixo está uma lista dessas funções.

• heapify - Esta função converte uma lista regular em um heap. No heap resultante, o menor elemento é empurrado para a posição de índice 0. Mas o restante dos elementos de dados não são necessariamente classificados.
• heappush - Esta função adiciona um elemento ao heap sem alterar o heap atual.
• heappop - Esta função retorna o menor elemento de dados do heap.
• heapreplace - Esta função substitui o menor elemento de dados por um novo valor fornecido na função.

Criando um Heap

Um heap é criado simplesmente usando uma lista de elementos com a função heapify. No exemplo abaixo, fornecemos uma lista de elementos e a função heapify reorganiza os elementos trazendo o menor elemento para a primeira posição.

import heapq

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

Quando o código acima é executado, ele produz o seguinte resultado -

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

Inserindo na pilha

Inserir um elemento de dados em um heap sempre adiciona o elemento no último índice. Mas você pode aplicar a função heapify novamente para trazer o elemento recém-adicionado ao primeiro índice somente se ele tiver o menor valor. No exemplo abaixo, inserimos o número 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 o código acima é executado, ele produz o seguinte resultado -

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

Removendo da pilha

Você pode remover o elemento no primeiro índice usando esta função. No exemplo abaixo, a função sempre removerá o elemento na posição de índice 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 o código acima é executado, ele produz o seguinte resultado -

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

Substituindo em um Heap

A função heapreplace sempre remove o menor elemento do heap e insere o novo elemento de entrada em algum lugar não fixado por nenhuma ordem.

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]