Heaps Binárias em Python OO

• Invariante de Estrutura: Árvore binária quase completa representada em array.
• Invariante de Ordem: Em Max-Heap, Pai ≥ Filho para todo nó.
• Eficiência: Operações básicas em O(log n) e construção em O(n).

class BinaryHeap:
    def __init__(self):
        self.heap = []
        self.comparacoes = 0
        self.trocas = 0

    def _pai(self, i): return (i - 1) // 2
    def _filho_esq(self, i): return 2 * i + 1
    def _filho_dir(self, i): return 2 * i + 2

    def _find_index(self, valor):
        # Busca linear instrumentada para auditoria real de custo O(n)
        for i, atual in enumerate(self.heap):
            self.comparacoes += 1
            if atual == valor: return i
        return -1

def insert(self, valor):
    self.heap.append(valor)
    self._sift_up(len(self.heap) - 1)

def _sift_up(self, i):
    while i > 0:
        p = self._pai(i)
        self.comparacoes += 1
        if self.heap[i] > self.heap[p]:
            print(f"Swap: {self.heap[i]} <-> {self.heap[p]}")
            self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
            self.trocas += 1
            i = p
        else:
            break

def extract_max(self):
    if not self.heap:
        return None
    if len(self.heap) == 1:
        return self.heap.pop()

    max_val = self.heap[0]
    self.heap[0] = self.heap.pop()
    self._sift_down(0)
    return max_val

def _sift_down(self, i):
    n = len(self.heap)
    while True:
        maior = i
        esq = self._filho_esq(i)
        dir = self._filho_dir(i)

        if esq < n:
            self.comparacoes += 1
            if self.heap[esq] > self.heap[maior]:
                maior = esq

        if dir < n:
            self.comparacoes += 1
            if self.heap[dir] > self.heap[maior]:
                maior = dir

        if maior == i:
            break

        print(f"Swap: {self.heap[i]} <-> {self.heap[maior]}")
        self.heap[i], self.heap[maior] = self.heap[maior], self.heap[i]
        self.trocas += 1
        i = maior

def contains(self, valor):
    # Custo: O(n). Busca linear exaustiva.
    for i in range(len(self.heap)):
        self.comparacoes += 1
        if self.heap[i] == valor: return True
    return False

def delete(self, valor):
    idx = self._find_index(valor)
    if idx == -1: return False

    ultimo = self.heap.pop()

    # Se o removido já era o último, a tarefa termina.
    if idx == len(self.heap): return True

    self.heap[idx] = ultimo

    # Decide a direção do reequilíbrio
    if idx > 0:
        self.comparacoes += 1
        if self.heap[idx] > self.heap[self._pai(idx)]:
            self._sift_up(idx)
        else:
            self._sift_down(idx)
    else:
        self._sift_down(idx)

    return True

def is_valid_heap(array):
    n = len(array)
    for i in range(n // 2):
        l, r = 2*i + 1, 2*i + 2
        if l < n and array[i] < array[l]: return False
        if r < n and array[i] < array[r]: return False
    return True

def build_heap(self, lista):
    self.heap = list(lista)
    # Começa do último nó pai e vai até a raiz
    for i in range((len(self.heap) // 2) - 1, -1, -1):
        self._sift_down(i)

def test_comparison(n):
    # Entrada crescente: desfavorável para inserção incremental em Max-Heap
    valores = list(range(n))
    
    # 1. Incremental
    h_inc = BinaryHeap()
    for v in valores: h_inc.insert(v)
    
    # 2. Floyd
    h_floyd = BinaryHeap()
    h_floyd.build_heap(valores)
    
    print(f"N={n} | Incremental Swaps: {h_inc.trocas} | Floyd Swaps: {h_floyd.trocas}")

def k_maiores(array, k):
    if k < 0: raise ValueError("k negativo")
    h = BinaryHeap()
    h.build_heap(array)
    limite = min(k, len(array))
    return [h.extract_max() for _ in range(limite)]

def test_comparison(n):
    valores = list(range(n))  # Entrada crescente: desfavorável para Max-Heap incremental

    h_inc = BinaryHeap()
    for v in valores:
        h_inc.insert(v)

    h_floyd = BinaryHeap()
    h_floyd.build_heap(valores)

    print(
        f"N={n} | "
        f"Incremental: trocas={h_inc.trocas}, comparacoes={h_inc.comparacoes} | "
        f"Floyd: trocas={h_floyd.trocas}, comparacoes={h_floyd.comparacoes}"
    )

test_comparison(1000)
test_comparison(10000)

• Arquitetura: Justificar a escolha do Array pela localidade de referência.
• Invariantes: Explicar como o _sift_down restaura a propriedade de heap.
• Decisões: Discutir o custo linear da busca arbitrária.
• Evidência: Apresentar a instrumentação e a tabela comparativa.

h = BinaryHeap()

# E3: Inserção
for v in [10, 4, 15, 20, 1]: h.insert(v)
print("Heap após inserções:", h.heap)

# E7: Validação
print("É heap válida?", is_valid_heap(h.heap))

# E4: Extração
while h.heap:
    print("Extraído:", h.extract_max(), "Restante:", h.heap)

# E8: Build-Heap Floyd
h.build_heap([3, 9, 2, 10, 7, 1])
print("Build heap Floyd:", h.heap)

# E5 e E6: Busca e Delete
print("Contains 7?", h.contains(7))
print("Delete 9:", h.delete(9))
print("Após delete 9:", h.heap)

# E10: K Maiores
print("Top 3:", k_maiores([8, 1, 5, 20, 13, 2], 3))

• Extract-Max: trata corretamente o caso de um único elemento?
• Delete: utiliza _find_index instrumentado e reequilibra corretamente?
• Sift-down: implementado integralmente com busca pelo maior filho?
• Floyd: construção realizada em O(n) sem inserções individuais?
• Instrumentação: comparacoes e trocas capturam o custo real?
• Saída: a bateria de testes gera as evidências necessárias para o vídeo?