1. 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 (\text{timestamp},\;\text{valor}). 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:
enqueue(x): insere na heap a tupla (\text{contador}, x) e incrementa 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 O(\log n).

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\)

Exercícios relacionados