Algoritmo de ordenação por heap (com Code in Python e C++)

O que é algoritmo de classificação de heap?

O Heap Sort é um dos algoritmos de ordenação mais populares e rápidos. Ele é baseado na estrutura de dados de uma árvore binária completa. Buscamos o elemento máximo e o colocamos no topo do heap máximo. Esse elemento é então colocado no nó pai da árvore binária.

Digamos que um array seja fornecido, dados = [10,5, 7, 9, 4, 11, 45, 17, 60].

Na matriz, se o i-ésimo (i=0,1,2,3…) índice for um nó pai, então, (2i+1) e (2i+2) serão os filhos esquerdo e direito. A criação de uma árvore binária completa com este array ficará assim:

Faremos o processo heapify do início ao fim do array. Inicialmente, se convertermos o array em uma árvore, ele se parecerá com o mostrado acima. Podemos ver que ele não mantém nenhuma propriedade de heap (min-heap ou max heap). Obteremos o array classificado executando o processo heapify para todos os nós.

Aplicação de classificação de heap

Aqui estão alguns usos do algoritmo de classificação de heap:

• A construção de “Filas Prioritárias” requer classificação de heap. Porque o heapsort mantém o elemento classificado após cada inserção ser feita.
• A estrutura de dados heap é eficiente para encontrar o k^th maior elemento em uma determinada matriz.
• O kernel do Linux usa a classificação de heap como padrão algoritmo de classificação pois tem complexidade espacial O(1).

Criar classificação de heap com exemplo

Aqui, construiremos um heap máximo a partir da seguinte árvore binária completa.

Os nós folha são 17, 60, 4, 11 e 45. Eles não possuem nós filhos. É por isso que são nós folha. Portanto, iniciaremos o método heapify a partir de seu nó pai. Aqui estão as etapas:

Passo 1) Selecione a subárvore mais à esquerda. Se os nós filhos forem maiores, troque o nó pai pelo nó filho.

Aqui o nó pai é 9. E os nós filhos são 17 e 60. Como 60 é o maior, 60 e 9 serão trocados para manter o pilha máxima.

Passo 2) Agora, a subárvore mais à esquerda está empilhada. O próximo nó pai é 7. Este pai tem dois nós filhos e o maior é 45. Portanto, 45 e 7 serão trocados.

Passo 3) Os nós 60 e 4 possuem o nó pai 5. Como “5” é menor que o nó filho 60, ele será trocado.

Passo 4) Agora, o nó 5 possui o nó filho 17,9. Isso não mantém a propriedade max heap. Então, 5 será substituído por 17.

Passo 5) O nó 10 será trocado por 60 e depois trocado por 17. O processo será semelhante ao seguinte.

Passo 6) Até a etapa 5, criamos o heap máximo. Cada nó pai é maior que seus nós filhos. O nó raiz possui o valor máximo (60).

Observação: Para criar o array classificado, precisamos substituir o nó com valor máximo por seu sucessor.

Este processo é denominado “extract max”. Como 60 é o nó máximo, fixaremos sua posição no índice 0 e criaremos o heap sem o nó 60.

Passo 7) À medida que o valor 60 é removido, o próximo valor máximo é 45. Faremos o processo “Extract Max” novamente do nó 45.

Desta vez obteremos 45 e substituiremos o nó raiz pelo seu sucessor 17.

Precisamos realizar “Extract Máx.”Até que todos os elementos sejam classificados.

Após realizar esses passos até que extracAo aplicarmos todos os valores máximos, obteremos a seguinte matriz.

O que é pilha binária?

Um Binary Heap é uma espécie de completo árvore binária estrutura de dados. Nesse tipo de estrutura em árvore, o nó pai é maior ou menor que os nós filhos. Se o nó pai for menor, o heap será chamado de “Min Heap” e se o nó pai for maior, o heap será chamado de “Max Heap”.

Aqui estão exemplos de heap mínimo e heap máximo.

Na figura acima, se você notar o “Min Heap”, o nó pai é sempre menor que seus nós filhos. No topo da árvore, podemos encontrar o menor valor 10.

Da mesma forma, para o “Max Heap”, o nó pai é sempre maior que os nós filhos. O elemento máximo está presente no nó principal do “Max Heap”.

O que é “Heapify”?

“Heapify” é o princípio do heap que garante a posição do nó. No Heapify, um heap máximo sempre mantém um relacionamento entre pai e filho, e esse nó pai será maior que os nós filhos.

Por exemplo, se um novo nó for adicionado, precisamos remodelar o heap. No entanto, podemos precisar alterar ou trocar os nós ou reorganizar o array. Esse processo de remodelaçãoping Um heap é chamado de "heapificação".

Aqui está um exemplo de como o heapify funciona:

Aqui estão as etapas para heapify:

Passo 1) Adicionado o nó 65 como filho direito do nó 60.

Passo 2) Verifique se o nó recém-adicionado é maior que o pai.

Passo 3) Como é maior que o nó pai, trocamos o filho certo pelo seu pai.

Como construir o Heap

Antes de construir a pilha ou empilhar uma árvore, precisamos saber como iremos armazená-la. Como o heap é uma árvore binária completa, é melhor usar um ordem para armazenar os dados do heap.

Digamos que um array contenha um total de n elementos. Se o “i”-ésimo índice for um nó pai, então o nó esquerdo estará no índice (2i+1), e o nó certo estará no índice (2i+2). Estamos assumindo que o índice do array começa em 0.

Usando isso, vamos armazenar um heap máximo em um array semelhante a seguinte:

O algoritmo heapify mantém a propriedade heap. Se o pai não tiver o valor extremo (menor ou maior), ele será trocado pelo nó filho mais extremo.

Aqui estão as etapas para heapificar um heap máximo:

Passo 1) Comece no nó folha.

Passo 2) Encontre o máximo entre pai e filhos.

Passo 3) Troque os nós se o nó filho tiver um valor maior que o pai.

Passo 4) Suba um nível.

Passo 5) Siga as etapas 2,3,4 até atingir o índice 0 ou classificar a árvore inteira.

Aqui está o pseudocódigo para heapify recursivo (heap máximo):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Apelido Code para ordenação por heap

Aqui está o pseudocódigo para o algoritmo de classificação de heap:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Exemplo de ordenação por heap Code in C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Saída:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Exemplo de ordenação por heap Code in Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Saída:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Análise de complexidade de tempo e espaço de Heap Sort

Há complexidade de tempo e complexidade de espaço que podemos analisar para a classificação de heap. Para complexidade de tempo, temos os seguintes casos:

1. Melhor Case
2. Caso Médio
3. Pior caso

O heap é implementado em uma árvore binária completa. Portanto, no nível inferior da árvore binária, estará o número máximo de nós. Se o nível inferior tiver n nós, o nível acima terá n/2 nós.

Neste exemplo, o Nível 3 possui quatro itens, o nível 2 possui dois itens e o nível 1 possui um item. Se houver um número total de n itens, a altura ou nível total será Folhas para₂(n). Portanto, a inserção de um único elemento pode levar no máximo iterações Log(n).

Quando queremos obter o valor máximo do heap, apenas pegamos o nó raiz. Então, novamente, execute o heapify. Cada heapify leva Folhas para₂(n) tempo. Extracatingir o máximo leva tempo O(1).

Melhor complexidade de tempo de caso para algoritmo de classificação de heap

Quando todos os elementos já estiverem classificados no array, levará O(n) tempo para construir o heap. Porque se a lista estiver ordenada, a inserção de um item levará um tempo constante que é O(1).

Portanto, levará O(n) tempo para criar um heap máximo ou heap mínimo na melhor das hipóteses.

Complexidade de tempo médio de caso para algoritmo de classificação de heap

Inserir um item ou extracA complexidade de tempo para o algoritmo de ordenação por heap é O(log(n)). Portanto, a complexidade de tempo média para o algoritmo de ordenação por heap é O(nlog(n)).

Pior caso de complexidade de tempo para algoritmo de classificação de heap

Semelhante ao caso médio, no pior cenário, poderíamos realizar heapify n vezes. Cada heapify custará O(log(n)) tempo. Portanto, a complexidade de tempo do pior caso será O(nlog(n)).

Complexidade espacial para algoritmo de classificação de heap

Heap sort é um algoritmo projetado no local. Isso significa que nenhuma memória extra ou temporária é necessária para executar a tarefa. Se observarmos a implementação, notaremos que utilizamos swap() para realizar a troca dos nós. Nenhuma outra lista ou matriz foi necessária. Portanto, a complexidade do espaço é O(1).

Perguntas Frequentes