Published

08/05/2026

Modified

22/04/2026

Algoritmos Gulosos Avançados: Intercalação Ótima (Huffman-like)

O problema da fusão inteligente de vetores (ou sequências) ilustra de forma categórica como os algoritmos gulosos dependem de prioridades sequenciais. Quando precisamos concatenar/intercalar iterativamente dezenas de coleções em uma só, a ordem faz toda a diferença estatística.

O Problema: Fusão em Cascata (Intercalação)

Imagine que temos vários vetores de diferentes tamanhos ordenados, e precisamos mesclá-los num único mega-vetor também ordenado. Sabemos que unir um vetor de tamanho M com um de tamanho K custa O(M + K) comparações diretas ao estilo do Merge Sort.

Se juntarmos os vetores mais compridos primeiro, eles logo de cara vão transbordar para um vetor muito grande. Nas etapas seguintes, esse “gigante” será processado repetidamente contra tudo o mais que restar. Somatórios de custo inflarão imensamente sob as repetições.

Estratégia Gulosa: Selecione, a cada passo imperativamente, os dois menores vetores disponíveis. Funda-os. Jogue o novo vetor resultante de volta no conjunto. Repita até que reste apenas 1.

Esse é o princípio raiz usado, por exemplo, na Codificação de Huffman em redes e compressão ZIP.

Árvore de Custo e Decisão (Mermaid)

Vejo o custo ao juntarmos 5 vetores de tamanhos hipotéticos: 10, 20, 30, 40, 50

Custo base nas comparações agregadas = 30 + 60 + 100 + 150 = 340 Custo Total. Tente fazer isso combinando o 50 com 40 logo de vez, os resultados piorariam verticalmente!

Implementação Inteligente: Priority Queue (Fila de Prioridade em C++)

Sempre precisar invocar um relógio para caçar e encontrar “os 2 menores” vetores numa lista crua em while/for a cada rodada é perigoso em performance, criando uma complexidade inerente de \(O(N^2)\). Como podemos sempre manter os menores num pedestal ou no topo disponíveis no exato momento, dinamicamente? Com uma Fila de Prioridades (Priority Queue / Heap). Em bibliotecas de C++ (<queue>), ele implementa nativamente o Heap.

#include <iostream>
#include <queue>
#include <vector>
#include <cassert>

// Criaremos um alias para um Min-Heap nativo
// A documentação do C++ define std::priority_queue como Max-Heap (o maior do topo),
// logo definimos um custom comparativo de "greater" para nos garantir o MENOR primeiro.
using MinHeap = std::priority_queue<int, std::vector<int>, std::greater<int>>;

int custoIntercalacaoOtima(std::vector<int> tamanhos_iniciais) {
    MinHeap heap;

    // População primária (O(N log N))
    for(int tam : tamanhos_iniciais) {
        heap.push(tam);
    }

    int custo_compara_total = 0;

    // Redução Gulosa passo a passo
    // Unindo 2 vira 1, então rodamos até restar 1
    while(heap.size() > 1) {
        // Sacando os 2 imediatos menores globais O(1) + Pop O(log N)
        int min1 = heap.top(); heap.pop();
        int min2 = heap.top(); heap.pop();

        int fusao_atual = min1 + min2;
        
        // A fusão gerou tráfego e trabalho operatório computado
        custo_compara_total += fusao_atual;

        // Injetando o novo combinado de volta para a fila bater com os remanescentes (O(log N))
        heap.push(fusao_atual);
    }

    return custo_compara_total;
}

void validacao_cenarios() {
    // Vetores originais
    std::vector<int> v1 = {10, 20, 30, 40, 50};
    // Esperado do diagrama acima: 30 + 60 + 100 + 150 = 340 de tráfego de mesclagem
    assert(custoIntercalacaoOtima(v1) == 340);
    
    // Outro teste simples
    std::vector<int> v2 = {4, 3, 2, 6}; // Menores são 2 e 3-> 5. Ai fila fica [4, 5, 6]. 4 e 5 -> 9. [6, 9] -> 15.
    // Total = 5 + 9 + 15 = 29
    assert(custoIntercalacaoOtima(v2) == 29);

    std::cout << "[✅] Testes de Heap e Mesclagem Múltipla passaram isoladamente.\n";
}

int main() {
    validacao_cenarios();
    return 0;
}

A complexidade despenca de tempos trágicos a robustez teórica de puramente \(O(N \log N)\) garantido pelo empilhamento estrito usando Priority Queues, sendo base canônica de otimização em torneios de programação globais.

Back to top