Pular para conteúdo

Aula 15 - Heaps Binários e Filas de Prioridade (Priority Queues) 🧱

Objetivo Pedagógico

Objetivo: Propriedade de heap (Min-Heap e Max-Heap), representação compacta em vetor contíguo (pai = i/2, filhos = 2i e 2i+1), operações heapify, inserção e extração em O(log n), e algoritmo HeapSort.

📑 1. Fundamentos Teóricos & Análise Estrutural

Propriedade de heap (Min-Heap e Max-Heap), representação compacta em vetor contíguo (pai = i/2, filhos = 2i e 2i+1), operações heapify, inserção e extração em O(log n), e algoritmo HeapSort. O domínio desta estrutura de dados é primordial para o desenvolvimento de software escalável, onde o consumo de ciclos de CPU e a alocação de memória RAM na heap determinam a viabilidade operacional do sistema.

📐 Representação Abstrata & Mapeamento em Memória

graph LR
    A["Entrada de Dados"] --> B["Heaps Binários e Filas de Prioridade (Priority Queues)"]
    B --> C["Operação / Manipulação de Ponteiros"]
    C --> D["Resultado / Complexidade Assintótica"]

    style A fill:#e3f2fd,stroke:#1565c0
    style B fill:#fff3e0,stroke:#e65100,stroke-width:2px
    style C fill:#e8f5e9,stroke:#2e7d32
    style D fill:#f3e5f5,stroke:#7b1fa2

🔍 Pilares e Propriedades Algorítmicas

Nesta unidade, exploramos formalmente: - Max-Heap e Min-Heap: Fundamento teórico indispensável para a correta aplicação computacional. - Fila de Prioridade: Fundamento teórico indispensável para a correta aplicação computacional. - Heapify O(log n): Fundamento teórico indispensável para a correta aplicação computacional. - HeapSort O(n log n): Fundamento teórico indispensável para a correta aplicação computacional. - Representação Vetorial: Fundamento teórico indispensável para a correta aplicação computacional.

🛠️ 2. Implementação Técnica em Linguagem C

Abaixo está o código de referência estruturado seguindo os padrões de boas práticas da linguagem C (ANSI C / C99), com gerenciamento dinâmico de memória e verificação de ponteiros nulos:

// Max-Heapify em Vetor
void heapify(int arr[], int n, int i) {
    int maior = i;
    int esq = 2 * i + 1;
    int dir = 2 * i + 2;

    if (esq < n && arr[esq] > arr[maior]) maior = esq;
    if (dir < n && arr[dir] > arr[maior]) maior = dir;

    if (maior != i) {
        int temp = arr[i]; arr[i] = arr[maior]; arr[maior] = temp;
        heapify(arr, n, maior);
    }
}

💡 Análise de Eficiência e Complexidade

  1. Complexidade Temporal: A implementação prioriza caminhos de execução diretos para atingir o menor custo assintótico possível.
  2. Gerenciamento de Memória: Toda alocação realizada na heap deve possuir uma rotina correspondente de liberação para assegurar vazamento zero de memória (zero memory leaks).
  3. Casos de Borda: Tratamento rigoroso de listas vazias, ponteiros nulos (NULL) e estouros de capacidade.

🎯 3. Próximos Passos & Sequência Didática