Complexidade do tempo de Heapsort

O tipo de heap, escrito como Heapsort, é um tipo de algoritmo de classificação. É preciso uma lista que é parcialmente ordenada e produz uma lista classificada a partir dela. Classificar pode estar ascendente ou descendente. Neste artigo, a classificação está ascendendo. Observe que o HEAPSORT não classifica uma lista incompletamente não classificada. Ele classifica uma lista parcialmente ordenada (classificada). Essa lista parcialmente ordenada é uma pilha. Neste artigo, o heap considerado é a pilha mínima (ascendente).

Uma pilha é chamada de "parcialmente ordenada" e não "parcialmente classificada". A palavra "classificar" significa pedidos completos (classificação completa). Uma pilha não é parcialmente ordenada arbitrariamente. Uma pilha é parcialmente ordenada após um critério (padrão), como mostrado abaixo.

Portanto, o HeapSort consiste em dois estágios: construir a pilha e extrair o elemento ordenado da parte superior da pilha. Na segunda etapa, após cada extração, a pilha é reconstruída. Cada reconstrução é mais rápida que o processo de construção original, pois a reconstrução é feita a partir de uma compilaçã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 depois produzir sua complexidade do tempo (veja o significado da complexidade do tempo abaixo). No final, a codificação é feita em c++.

Heap mínimo

Uma pilha pode ser uma pilha mínima ou uma pilha máxima. Um max-heap é aquele em que o primeiro elemento é o elemento mais alto, e toda a árvore ou lista correspondente é parcialmente ordenada em ordem decrescente. Um min-heap é aquele em que o primeiro elemento é o menor elemento, e toda a lista é parcialmente ordenada em ordem crescente. Neste artigo, apenas a pilha mínima é considerada. Nota: No tópico da pilha, um elemento também é chamado de nó.

Uma pilha é uma árvore binária completa. A árvore binária pode ser expressa como uma matriz (lista); Leia de cima para baixo e da esquerda para a direita. A propriedade Heap para um min-heap é que um nó pai é menor ou igual a cada um de seus dois filhos. Um exemplo de uma lista não ordenada é:

9	19	24	5	3	11	14	22	7	6	17	15	nulo	nulo	nulo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

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. Estritamente falando, os elementos nulos não fazem parte da lista (árvore). Esta lista não tem ordem, então ainda não é uma pilha. Ele se tornará uma pilha quando tiver pedidos parciais, de acordo com a propriedade Heap.

Relação entre nós e índices

Lembre -se, uma pilha é uma árvore binária completa antes de ter a configuração da pilha (propriedade Heap). A lista anterior ainda não é uma pilha, porque os elementos não obedecem à propriedade Heap. Torna-se uma pilha após reorganizar elementos em ordem parcial de acordo com a propriedade Min-Heap. A ordem parcial pode ser vista como classificação parcial (embora a palavra "classificar" signifique pedidos completos).

Se uma árvore binária é uma pilha ou não, cada pai tem dois filhos, exceto os nós da folha (último). 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 esquerdo estará no índice:

2*i + 1

E a criança certa está no índice:

2*i + 2

Isto é 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 criança direita no índice 2 × 1+2 = 4; e assim por diante.

Pela propriedade Min-Heap, um pai em I é menor ou igual à criança esquerda a 2i+1 e menor ou igual à criança certa a 2i+2.

Pilha

Heapcifying significa construir uma pilha. Significa reorganizar os elementos de uma lista (ou árvore correspondente) para que eles satisfazem a propriedade Heap. No final do processo de peso, a lista ou a árvore é uma pilha.

Se a lista não classificada anterior estiver pesada, ela se tornará:

3	5	11	7	6	15	14	22	9	19	17	24	nulo	nulo	nulo
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14

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

Observe que o menor e o primeiro elemento é 3. O restante dos elementos seguem de maneira ascendente, mas ondulada. Se as crianças esquerda e direita nas posições 2i+1 e 2i+2 forem maiores ou iguais ao pai em I, então isso é um min-heap. Isso não é pedido completo ou classificação. Esta é uma ordem parcial, de acordo com a propriedade Heap. É daqui que o próximo estágio para o tipo de heap começa.

Heapify Time Complexity

A complexidade do 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. A mais eficiente e mais rápida dividem continuamente a lista por dois, verificando os elementos do fundo e depois fazendo alguma troca 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 (troca) é n. A complexidade do tempo para a pesagem é dada anteriormente como:

Sobre)

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 na mancha, seguido de parênteses. Dentro dos parênteses está a expressão para o possível número maior de operações.

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

Ilustração Heapsort

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

9 19 24 5 3 11 14 22 7 6 17 15

O Min-Heap produzido a partir da lista é:

3 5 11 7 6 15 14 22 9 19 17 24

A primeira etapa do HeapSort é produzir o heap que foi produzido. Esta é uma lista parcialmente ordenada. Não é uma lista classificada (completamente classificada).

O segundo estágio consiste em remover o mínimo elemento, que é o primeiro elemento, a partir da pilha, re-animando a pilha restante e removendo os menores elementos nos resultados. O menor elemento é sempre o primeiro elemento na pilha re-heapificada. 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.

No final, a nova matriz teria todos os elementos classificados (completamente), em ordem crescente; e não mais parcialmente pedido.

Na segunda etapa, a primeira coisa a fazer é remover 3 e colocá -lo na nova matriz. Os resultados são:

3

e

5 11 7 6 15 14 22 9 19 17 24

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

5 6 7 9 15 14 22 11 19 17 24

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

3 5

e

6 7 9 15 14 22 11 19 17 24

Afilar o conjunto restante daria:

6 7 9 15 14 22 11 19 17 24

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

3 5 6

e

7 9 15 14 22 11 19 17 24

Afilar o conjunto restante daria:

7 9 11 14 22 15 19 17 24

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

3 5 6 7

e

9 11 14 22 15 19 17 24

Atenda o conjunto restante fornece:

9 11 14 22 15 19 17 24

Extrair 9 e adicionar à nova lista, fornece os resultados:

3 5 6 7 9

e

11 14 22 15 19 17 24

Atenda o conjunto restante fornece:

11 14 17 17 15 19 22 24

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

3 5 6 7 9 11

e

14 17 15 19 22 24

Afilar o conjunto restante daria:

14 17 15 19 22 24

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

3 5 6 7 9 11 14

e

17 15 19 22 24

Afilar o conjunto restante daria:

15 17 19 22 24

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

3 5 6 7 9 11 14 15

e

17 19 22 24

Afilar o conjunto restante daria:

17 19 22 24

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

3 5 6 7 9 11 14 15 17

e

19 22 24

Afilar o conjunto restante daria:

19 22 24

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

3 5 6 7 9 11 14 15 17 19

e

22 24

Atenda o conjunto restante fornece:

22 24

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

3 5 6 7 9 11 14 15 17 19 22

e

24

Atenda o conjunto restante fornece:

24

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

3 5 6 7 9 11 14 15 17 19 22 24

e

- - -

A matriz de heap agora está vazia. Todos os elementos que tinham no começo estão agora na nova matriz (lista) e classificados.

Algoritmo HeapSort

Embora o leitor possa ter lido nos livros didáticos que o HeapSort consiste em dois estágios, o HeapSort ainda pode ser visto como consistindo em um estágio, que encolher iterativamente a matriz dada. Com isso, o algoritmo para classificar com HeapSort é o seguinte:

• Errar a lista não classificada.
• Extraia o primeiro elemento da pilha e coloque -o como o primeiro elemento da nova lista.
• Errar a lista restante.
• Extraia o primeiro elemento do novo heap e coloque como o 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 é classificada.

Complexidade do tempo de heapsort

A abordagem de um estágio é usada para determinar a complexidade do tempo para Heapsort. Suponha que há 8 elementos não classificados a serem classificados.

O possível número máximo de operações para intensificar os 8 elementos é 8.
O possível número máximo de operações para alimentar os 7 elementos restantes é 7.
O possível número máximo de operações para alimentar os 6 elementos restantes é 6.
O possível número máximo de operações para alimentar os 5 elementos restantes é 5.
O possível número máximo de operações para alimentar os 4 elementos restantes é 4.
O possível número máximo de operações para aumentar os 3 elementos restantes é 3.
O possível número máximo de operações para alimentar os 2 elementos restantes é 2.
O possível número máximo de operações para alimentar o 1 elemento restante é 1.

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

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

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

36/8 = 4.5

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

24 = 8 x 3
=> 24 = 8 x log₂8

Desde o log₂8 = 3.

Em geral, a complexidade média do tempo do caso para Heapsort é:

Sobre.log2n)

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 extrair o primeiro elemento foi ignorada. Sobre o tema da complexidade do tempo, as operações que levam relativamente curtas são ignoradas.

Codificação em c++

Na biblioteca de algoritmo de C ++, há uma função make_heap (). A sintaxe é:

modelo
constexpr void make_heap (RandomAccessIterator primeiro, RandomAccessIterator Último, compare comp);

Leva o iterador apontando para o primeiro elemento de um vetor como seu primeiro argumento e depois o iterador apontando logo além do fim do vetor como seu último argumento. Para a lista anterior, a sintaxe seria usada da seguinte maneira para obter uma pilha mínima:

vetor vtr = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vetor:: iterator iterb = vtr.começar();
vetor:: iterator itere = vtr.fim();
make_heap (iterb, itre, maior());

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

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

Frente de referência constExpr ();

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

Apagação do iterador constExpr (posição const_iterator)

Para adicionar um elemento na parte traseira de um vetor (próximo elemento), use a sintaxe do vetor:

constexpr void push_back (const t & x);

O início do programa é:

#incluir
#incluir
#incluir
usando namespace std;

O algoritmo e as bibliotecas de vetores estão incluídas. Em seguida, no programa é a função HeapSort (), que é:

Heapsort vazio (vetor & Oldv, vetor & newv)
if (Oldv.tamanho ()> 0)
vetor:: iterator iterb = Oldv.começar();
vetor:: iterator itere = Oldv.fim();
make_heap (iterb, itre, maior());
int próximo = Oldv.frente();
Oldv.apagar (iterb);
newv.push_back (próximo);
heapsort (Oldv, newv);

É uma função recursiva. Ele usa a função make_heap () da biblioteca de algoritmo C ++. O segundo segmento de código na definição da função extrai o primeiro elemento do antigo vetor após o edifício da 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 é:

int main (int argc, char ** argv)

vetor Oldv = 9, 19, 24, 5, 3, 11, 14, 22, 7, 6, 17, 15;
vetor newv;
heapsort (Oldv, newv);
para (int i = 0; icout << newV[i] << ";

cout << endl;
retornar 0;

A saída é:

3 5 6 7 9 11 14 15 17 19 22 24

classificado (completamente).

Conclusão

O artigo discutido em detalhes a natureza e a função do tipo de heap comumente conhecida como heapsort, como um algoritmo de classificação. Heapify Time Complexity, Heapsort Ilustração e Heapsort como um algoritmo foram cobertos e apoiados por exemplos. A complexidade média do tempo para um programa HeapSort bem escrito é O (nlog (n))