Heaps Binárias em Python OO

▼

EX.01

Motivação Computacional

Análise de operações críticas no CPU Scheduler.

Cenário: Escalonamento de Processos. O sistema deve atender primeiro a maior prioridade. A Heap equilibra inserção e extração em tempo logarítmico.

Operação	Lista Ordenada	Heap Máxima
Nova Tarefa	O(n)	O(log n)
Próxima Tarefa	O(1)	O(log n)
Busca/Cancelamento	O(n)	O(n)

▼

EX.02

Classe BinaryHeap e Índices

Instrumentação: Comparações (>) e Trocas (swaps no array).

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

    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

▼

EX.03

Inserção e Sift-up

def _sift_up(self, i):
    while i > 0:
        p = self._pai(i)
        self.comparacoes += 1
        if self.heap[i] > self.heap[p]:
            if self.debug: print(f"Swap Up: {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

▼

EX.04

Extract-Max Sucessivo

def extract_max(self):
    if not self.heap: return None
    if len(self.heap) == 1: return self.heap.pop()
    root = self.heap[0]
    self.heap[0] = self.heap.pop()
    self._sift_down(0)
    return root

▼

EX.08

Floyd O(n) vs Floyd-Warshall

Aviso: Aqui, "Floyd" refere-se à construção bottom-up da heap, não ao algoritmo de caminhos mínimos em grafos.

def build_heap(self, array):
    self.heap = list(array)
    for i in range((len(self.heap)//2)-1, -1, -1):
        self._sift_down(i)

▼

EX.11

Análise Empírica Real

n	Incremental (Trocas)	Floyd (Trocas)	Ganho
1.000	7.987	992	~8x
10.000	113.631	9.992	~11x

▼

ARQUIVO

binary_heap.py: Single Source of Truth

import math

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

    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 insert(self, v):
        self.heap.append(v)
        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]:
                if self.debug: print(f"Swap Up: {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()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return root

    def _sift_down(self, i):
        n = len(self.heap)
        while True:
            maior = i
            l, r = self._filho_esq(i), self._filho_dir(i)
            if l < n:
                self.comparacoes += 1
                if self.heap[l] > self.heap[maior]: maior = l
            if r < n:
                self.comparacoes += 1
                if self.heap[r] > self.heap[maior]: maior = r
            if maior != i:
                if self.debug: print(f"Swap Down: {self.heap[i]} <-> {self.heap[maior]}")
                self.heap[i], self.heap[maior] = self.heap[maior], self.heap[i]
                self.trocas += 1
                i = maior
            else: break

    def build_heap(self, arr):
        self.heap = list(arr)
        for i in range((len(self.heap)//2)-1, -1, -1): self._sift_down(i)

    def contains(self, v):
        for x in self.heap:
            self.comparacoes += 1
            if x == v: return True
        return False

    def delete(self, v):
        idx = -1
        for i, val in enumerate(self.heap):
            self.comparacoes += 1
            if val == v: idx = i; break
        if idx == -1: return False
        ultimo = self.heap.pop()
        if idx == len(self.heap): return True
        self.heap[idx] = ultimo
        if idx > 0 and self.heap[idx] > self.heap[self._pai(idx)]: self._sift_up(idx)
        else: self._sift_down(idx)
        return True

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

if __name__ == "__main__":
    h = BinaryHeap()
    print("--- Bateria de Borda ---")
    print("Extract em vazia:", h.extract_max())
    print("Delete inexistente:", h.delete(99))
    h.insert(10)
    print("Unitária válida?", is_valid_heap(h.heap))
    h.insert(10) # Duplicado
    print("Duplicado válido?", is_valid_heap(h.heap))

▼

CHECK

Validação de Conformidade

Debug Flag: Permite silenciar prints em N grandes?
Single File: Arquivo unificado disponível no final?
Edge Cases: Casos de vazia, unitária e duplicados tratados?

Página finalizada com rigor de engenharia total.

Heaps Binárias em Python OO - TP1a