Algoritmos e Estruturas de Dados III - AED3 05 05 Seleção por substituição

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2021 ---------------------- Na intercalação balanceada, quanto maior forem os blocos ordenados gerados na fase de distribuição, menor será a quantidade de intercalações necessárias. Para gerarmos blocos maiores na distribuição, podemos usar alguma estrutura de dados de apoio como um heap de mínimo. ---------------------- Como você viu nas páginas anteriores, quanto maiores forem os segmentos, menos intercalações precisaremos fazer. Porém, nós sabemos que o tamanho dos segmentos é limitado pela capacidade de ordenação em memória principal. Na página anterior, de segmentos de tamanho variável, vimos como usar segmentos de tamanho variável quando tivermos a sorte de eles estarem ordenados entre si. Bom, isso é não é bem verdade... nós não precisamos contar com a sorte para gerar segmentos maiores. Podemos usar uma estrutura de dados como uma fila de prioridades para gerar, de forma planejada, segmentos maiores. Veremos como fazer isso aqui, usando um heap de mínimo, que é uma forma de fila de prioridades. Com esse heap de mínimo, nós poderemos usar uma estrutura de tamanho N para gerar segmentos de tamanho maior que N.