Complexidade de tempo do heapsort

Um heap é referido como “parcialmente ordenado” e não “parcialmente ordenado”. A palavra “sort” significa ordenação completa (ordenação completa). Um heap não é parcialmente ordenado arbitrariamente. Um heap é parcialmente ordenado seguindo um critério (padrão), conforme mostrado abaixo.

Assim, o heapsort consiste em duas etapas: construir o heap e extrair o elemento ordenado do topo do heap. Na segunda etapa, após cada extração, o heap é reconstruído. Cada reconstrução é mais rápida do que o processo de construção original, pois a reconstrução é feita a partir de uma construção anterior, onde um elemento foi removido. E com isso, o heapsort classifica uma lista completamente não classificada.

O objetivo deste artigo é explicar brevemente o heapsort e então produzir sua complexidade de tempo (veja o significado de complexidade de tempo abaixo). No final, a codificação é feita em C++.

Pilha Mínima

Um heap pode ser um heap mínimo ou um heap máximo. Um heap máximo é aquele em que o primeiro elemento é o elemento mais alto e toda a árvore ou lista correspondente é parcialmente ordenada em ordem decrescente. Um heap mínimo é aquele em que o primeiro elemento é o menor elemento e toda a lista é parcialmente ordenada em ordem crescente. Neste artigo, apenas o heap mínimo é considerado. Nota: no tópico do heap, um elemento também é chamado de nó.

Um heap é uma árvore binária completa. A árvore binária pode ser expressa como um array (lista); leia de cima para baixo e da esquerda para a direita. A propriedade heap para um heap mínimo é que um nó pai é menor ou igual a cada um de seus dois filhos. Um exemplo de lista não ordenada é:

A primeira linha desta tabela são os elementos da matriz. Na segunda linha estão os índices baseados em zero. Esta lista de elementos pode ser expressa como uma árvore. Os elementos nulos foram adicionados para fazer uma árvore binária completa. A rigor, os elementos nulos não fazem parte da lista (árvore). Esta lista não tem ordem, então ainda não é um heap. Ele se tornará um heap quando tiver ordenação parcial, de acordo com a propriedade do heap.

Relação entre nós e índices

Lembre-se, um heap é uma árvore binária completa antes de ter a configuração do heap (propriedade do heap). A lista anterior ainda não é um heap, pois os elementos não obedecem à propriedade heap. Ele se torna um heap depois de reorganizar os elementos em ordem parcial de acordo com a propriedade min-heap. A ordem parcial pode ser vista como ordenação parcial (embora a palavra “ordenar” signifique ordenação completa).

Quer uma árvore binária seja um heap ou não, cada pai tem dois filhos, exceto os nós folha (últimos). Existe uma relação matemática entre os índices entre cada pai e seus filhos. É o seguinte: Se o pai estiver no índice i, o filho da esquerda estará no índice:

e o filho certo está no índice:

Isso é para indexação baseada em zero. E assim, um pai no índice 0 tem seu filho esquerdo no índice 2×0+1=1 e seu filho direito em 2×0+2=2. Um pai no índice 1 tem seu filho esquerdo no índice 2×1+1=3 e o filho direito no índice 2×1+2=4; e assim por diante.

Pela propriedade min-heap, um pai em i é menor ou igual ao filho da esquerda em 2i+1 e menor ou igual ao filho da direita em 2i+2.

Pilha

Amontoar significa construir uma pilha. Significa reorganizar os elementos de uma lista (ou árvore correspondente) para que eles satisfaçam a propriedade do heap. No final do processo de heap, a lista ou árvore é um heap.

Se a lista não classificada anterior for empilhada, ela se tornará:

Nota: existem 12 elementos e não 15 na lista. Na segunda linha estão os índices. No processo de construção do heap, os elementos precisavam ser verificados e alguns trocados.

Observe que o menor e o primeiro elemento é 3. O restante dos elementos segue de maneira ascendente, mas ondulante. Se os filhos esquerdo e direito nas posições 2i+1 e 2i+2 forem maiores ou iguais ao pai em i, então este é um heap mínimo. Isso não é ordenação ou classificação completa. Esta é uma ordenação parcial, de acordo com a propriedade heap. É a partir daqui que começa a próxima etapa para a classificação de heap.

Complexidade de tempo de amontoar

A complexidade de tempo é o tempo de execução relativo de algum código. Pode ser visto como o número de operações principais para que esse código seja concluído. Existem diferentes algoritmos para construção de heap. Os mais eficientes e mais rápidos dividem continuamente a lista por dois, verificando os elementos de baixo para cima e depois fazendo algumas trocas de elementos. Seja N o número de elementos práticos na lista. Com este algoritmo, o número máximo de operações principais (swapping) é N. A complexidade de tempo para heapificação é dada anteriormente como:

Onde n é N e é o número máximo possível de operações principais. Essa notação é chamada de notação Big-O. Começa com O em maiúsculo, seguido de parênteses. Dentro dos parênteses está a expressão para o maior número possível de operações.

Lembre-se: a adição pode se tornar multiplicação se a mesma coisa que está sendo adicionada continuar se repetindo.

Ilustração Heapsort

A lista não classificada anterior será usada para ilustrar o heapsort. A lista dada é:

O min-heap produzido a partir da lista é:

O primeiro estágio no heapsort é produzir o heap que foi produzido. Esta é uma lista parcialmente ordenada. Não é uma lista ordenada (completamente ordenada).

A segunda etapa consiste em remover o menor elemento, que é o primeiro elemento, do heap, reagrupar o heap restante e remover os menores elementos nos resultados. O menor elemento é sempre o primeiro elemento no heap reagrupado. Os elementos não são removidos e jogados fora. Eles podem ser enviados para uma matriz diferente na ordem em que são removidos.

Ao final, o novo array teria todos os elementos ordenados (completamente), em ordem crescente; e não mais apenas parcialmente ordenado.

Na segunda etapa, a primeira coisa a fazer é remover 3 e colocá-lo no novo array. Os resultados são:

e

Os elementos restantes devem ser empilhados antes que o primeiro elemento seja extraído. A pilha dos elementos restantes pode se tornar:

Extrair 5 e adicionar à nova lista (array) fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 6 e adicionar à nova lista (array) fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 7 e adicioná-lo à nova lista fornece os resultados:

e

Ao empilhar o conjunto restante, obtém-se:

Extraindo 9 e adicionando à nova lista, dá os resultados:

e

Ao empilhar o conjunto restante, obtém-se:

Extrair 11 e adicioná-lo à nova lista fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 14 e adicioná-lo à nova lista fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 15 e adicioná-lo à nova lista fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 17 e adicioná-lo à nova lista fornece os resultados:

e

Acumular o conjunto restante daria:

Extrair 19 e adicioná-lo à nova lista fornece os resultados:

e

Ao empilhar o conjunto restante, obtém-se:

Extrair 22 e adicioná-lo à nova lista fornece os resultados:

e

Ao empilhar o conjunto restante, obtém-se:

Extrair 24 e adicioná-lo à nova lista fornece os resultados:

e

A matriz de heap agora está vazia. Todos os elementos que tinha no início estão agora no novo array (lista) e ordenados.

Algoritmo de Heapsort

Embora o leitor possa ter lido em livros didáticos que o heapsort consiste em dois estágios, o heapsort ainda pode ser visto como consistindo em um estágio, que reduz iterativamente o array fornecido. Com isso, o algoritmo para ordenar com heapsort é o seguinte:

• Empilhe a lista não classificada.
• Extraia o primeiro elemento do heap e coloque-o como o primeiro elemento da nova lista.
• Empilhe a lista restante.
• Extraia o primeiro elemento do novo heap e coloque como próximo elemento da nova lista.
• Repita as etapas anteriores em ordem até que a lista de heap esteja vazia. No final, a nova lista é ordenada.

Complexidade de tempo de heapsort adequada

A abordagem de um estágio é usada para determinar a complexidade de tempo para heapsort. Suponha que existam 8 elementos não ordenados a serem ordenados.

O número máximo possível de operações é:

A média desses números de operações é:

Observe que os últimos quatro heaps na ilustração anterior não foram alterados quando o primeiro elemento foi removido. Alguns dos heaps anteriores também não foram alterados quando o primeiro elemento foi removido. Com isso, um melhor número médio de operações principais (swappings) é 3 e não 4,5. Assim, um melhor número médio total de operações principais é:

desde log _dois 8 = 3.

Em geral, a complexidade média de tempo de caso para heapsort é:

Onde o ponto significa multiplicação e n é N, o número total de elementos na lista (qualquer lista).

Observe que a operação de extração do primeiro elemento foi ignorada. No tópico de Complexidade de Tempo, as operações que levam tempos relativamente curtos são ignoradas.

Codificando em C++

Na biblioteca de algoritmos de C++, existe uma função make_heap(). A sintaxe é:

Ele usa o iterador apontando para o primeiro elemento de um vetor como seu primeiro argumento e, em seguida, o iterador apontando logo além do final do vetor como seu último argumento. Para a lista não classificada anterior, a sintaxe seria usada da seguinte maneira para obter um heap mínimo:

Este código altera um conteúdo vetorial para uma configuração mínima de heap. Nos seguintes vetores C++, dois vetores serão usados ​​em vez de dois arrays.

Para copiar e retornar o primeiro elemento de um vetor, use a sintaxe de vetor:

Para remover o primeiro elemento de um vetor e jogá-lo fora, use a sintaxe de vetor:

Para adicionar um elemento na parte de trás de um vetor (próximo elemento), use a sintaxe de vetor:

O início do programa é:

O algoritmo e as bibliotecas de vetores estão incluídos. A seguir no programa está a função heapsort(), que é:

É uma função recursiva. Ele usa a função make_heap() da biblioteca de algoritmos C++. O segundo segmento de código na definição da função extrai o primeiro elemento do vetor antigo após a construção do heap e adiciona como o próximo elemento para o novo vetor. Observe que na definição da função, os parâmetros vetoriais são referências, enquanto a função é chamada com os identificadores (nomes).

Uma função principal C++ adequada para isso é:

A saída é:

ordenado (completamente).

Conclusão

O artigo discutiu em detalhes a natureza e a função do Heap Sort comumente conhecido como Heapsort, como um algoritmo de ordenação. Heapify Time Complexity, Heapsort ilustração e Heapsort como algoritmo foram cobertos e apoiados por exemplos. A complexidade de tempo média para um programa heapsort bem escrito é O(nlog(n))