- Implemente uma fila usando uma min-heap como estrutura sobrejacente.
Passo 1
O enunciado pede para implementar uma fila (FIFO) usando uma min-heap por baixo dos panos. O conteúdo envolvido é estrutura de dados (fila e heap), e vamos precisar usar a propriedade da min-heap de sempre remover o elemento de menor “chave”. Como a fila retira o elemento mais antigo, atribuímos a cada enfileiramento uma chave crescente (timestamp) para simular a ordem de chegada.
Passo 2
A ideia central é armazenar na min-heap tuplas do tipo
. Mantemos um contador interno que começa em zero e é incrementado a cada
enqueue
. Como a min-heap ordena por timestamp, o extract_min
sempre retorna o elemento com menor timestamp, ou seja, o mais antigo, respeitando FIFO.Passo 3
Definimos as operações da fila:
– e incrementa
–
–
–
Cada operação de inserção ou remoção na min-heap tem custo .
–
enqueue(x)
: insere na heap a tupla
contador
.–
dequeue()
: faz extract_min
na heap e retorna o campo valor
da tupla retornada.–
front()
: olha o topo da heap sem remover (peek) e retorna o valor
.–
is_empty()
: verifica se o tamanho da heap é zero.Cada operação de inserção ou remoção na min-heap tem custo
Passo 4
Segue um exemplo de implementação em Python usando o módulo
heapq
:import heapq
class FilaMinHeap:
def __init__(self):
self._heap = [] # lista interna da heap
self._contador \(=0\) # timestamp incremental
def enqueue(self, x):
# insere tupla (timestamp, valor)
heapq.heappush(self._heap, (self._contador, x))
self._contador \(+=1\)
def dequeue(self):
if not self._heap:
raise IndexError("dequeue from empty queue")
timestamp, valor = heapq.heappop(self._heap)
return valor
def front(self):
if not self._heap:
raise IndexError("front from empty queue")
timestamp, valor = self._heap[0]
return valor
def \(is_empty\)(self):
return len(self._heap) \(==0\)
Resposta
import heapq
class FilaMinHeap:
def __init__(self):
self._heap = []
self._contador \(=0\)
def enqueue(self, x):
heapq.heappush(self._heap, (self._contador, x))
self._contador \(+=1\)
def dequeue(self):
if not self._heap:
raise IndexError("dequeue from empty queue")
_, valor = heapq.heappop(self._heap)
return valor
def front(self):
if not self._heap:
raise IndexError("front from empty queue")
_, valor = self._heap[0]
return valor
def \(is_empty\)(self):
return len(self._heap) \(==0\)