Algoritmo de classificação de heap (com código em Python e C++)

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

Heap Sort é um dos algoritmos de classificação mais populares e mais rápidos. Ele é baseado na estrutura completa de dados da árvore binária. Procuraremos o elemento máximo e o colocaremos no topo do heap máximo. Vamos colocá-lo 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:

Algoritmo de classificação de heap

Nós faremos o eleapify processo do início ao fim da matriz. 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 fazendo o heapify processo 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 kth 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 O (1) espaço complexity.

Criar classificação de heap com exemplo

Aqui, construiremos um heap máximo a partir do seguintewing árvore binária completa.

Criar classificação de heap com exemplo

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. Então, vamos começar o eleapify método 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.

Criar classificação de heap com exemplo

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.

Criar classificação de heap com exemplo

Criar classificação de heap com exemplo

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

Criar classificação de heap com exemplo

Criar classificação de heap com exemplo

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.

Criar classificação de heap com exemplo

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

Criar classificação de heap com exemplo

Criar classificação de heap com exemplo

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).

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

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

Criar classificação de heap com exemplo

Criar classificação de heap com exemplo

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

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

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

Depois de seguir essas etapas até extrair todos os valores máximos, obteremos o seguintewing matriz.

Criar classificação de heap com exemplo

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.

Pilha mínima e pilha máxima
Pilha mínima e pilha máxima

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 é “Eleapify"?

"Eleapify”é o princípio do heap que garante a posição do nó. Em Eleapify, 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, precisaremos remodelar o heap. No entanto, podemos precisar alterar ou trocar os nós ou reorganizar o array. Este processo de remodelar uma pilha é chamado de “eleapify".

Aqui está um exemplo de como eleapify obras:

Adicionando um novo nó e eleapify
Adicionando um novo nó e eleapify

Aqui estão os passos para eleapify:

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 eleapify 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 seguimento semelhante a um arraywing:

Representação baseada em array do Max Heap
Representação baseada em array do heap máximo

O eleapify algoritmo 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 os passos para eleapify uma pilha máxima:

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 ele recursivoapify (pilha máxima):

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)

Pseudocódigo para classificação de 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 código de classificação de heap em 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 código de classificação de heap em 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

Tempo e Espaço Complexanálise de qualidade de Heap Sort

Há Tempo complexity and Space complexcapacidade que podemos analisar para a classificação de heap. Por hora complextemos o seguintewing casos:

  1. Melhor caso
  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.

Tempo e Espaço ComplexAnálise de cidade

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 para2(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 eleapify toma Folhas para2(n) tempo. Extrair o máximo leva tempo O(1).

Melhor Caso Time Complexcapacidade 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.

Tempo Médio do Caso Complexcapacidade para algoritmo de classificação de heap

Inserir um item ou extrair um custo máximo O(log(n)) tempo. Então, o tempo médio do caso complexA capacidade para o algoritmo de classificação de heap é O(nlog(n)).

Pior Caso Tempo Complexcapacidade para algoritmo de classificação de heap

Semelhante ao caso médio, no pior cenário, poderíamos realizar eleapify n vezes. Cada eleapify custará O (log (n)) tempo. Então, o pior momento complexserá O(nlog(n)).

Espaço Complexcapacidade 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. Então, o espaço complexidade é O(1).