Estrutura de dados heap: o que é heap? Heap mínimo e máximo (exemplo)

O que é uma pilha?

Heap é uma estrutura de dados em árvore especializada. O heap compreende o nó superior denominado raiz (pai). Seu segundo filho é o filho esquerdo da raiz, enquanto o terceiro nó é o filho direito da raiz. Os nós sucessivos são preenchidos da esquerda para a direita. A chave do nó pai é comparada com a de seu filho e ocorre um arranjo adequado. A árvore é fácil de visualizar onde cada entidade é chamada de nó. O nó possui chaves exclusivas para identificação.

Por que você precisa da estrutura de dados Heap?

Aqui estão os principais motivos para usar a estrutura de dados Heap:

A estrutura de dados heap permite exclusão e inserção em tempo logarítmico – O(log₂não).
Os dados na árvore são formados em uma ordem específica. Além de atualizar ou consultar coisas como máximo ou mínimo, o programador pode encontrar relacionamentos entre o pai e o filho.
Você pode aplicar o conceito de Modelo de Objeto de Documento para ajudá-lo a compreender a estrutura de dados heap.

Tipos de pilhas

A estrutura de dados heap possui vários algoritmos para lidar com inserções e remover elementos em uma estrutura de dados heap, incluindo Priority-Queue, Binary-Heap, Binomial Heap e Classificação de heap.

Fila de prioridade: É uma estrutura de dados abstrata contendo objetos priorizados. Cada objeto ou item tem uma prioridade pré-estabelecida para ele. Portanto, o objeto ou item com maior prioridade recebe o serviço antes dos demais.
Heap binário: Os heaps binários são adequados para operações simples de heap, como exclusões e inserções.
Heap binomial: Um heap binomial consiste em uma série de coleções de árvores binomiais que compõem o heap. A árvore Binomial Heap não é uma árvore comum, pois é rigorosamente definida. O número total de elementos em uma árvore binomial sempre possui 2ⁿ nós.
Classificação de heap: Ao contrário da maioria dos algoritmos de classificação, o heap-sort usa espaço O(1) para sua operação de classificação. É um algoritmo de classificação baseado em comparação onde a classificação ocorre em ordem crescente, primeiro transformando-a em um heap máximo. Você pode considerar um Heapsort como uma árvore de pesquisa binária de qualidade atualizada.

Normalmente, uma estrutura de dados heap emprega duas estratégias. Para entrada 12 – 8 – 4 – 2 e 1

Min Heap – menor valor no topo
Max Heap – valor mais alto no topo

Pilha Mínima

Na estrutura Min Heap, o nó raiz tem um valor igual ou menor que os filhos desse nó. Este nó de heap de um Min Heap contém o valor mínimo. Resumindo, sua estrutura min-heap é completa árvore binária.

Depois de ter uma pilha mínima em uma árvore, todas as folhas são candidatas viáveis. No entanto, você precisa examinar cada uma das folhas para obter o valor exato do Max-heap.

Exemplo de pilha mínima

Nos diagramas acima, você pode notar uma sequência clara da raiz ao nó mais baixo.

Suponha que você armazene os elementos em Array Array_N[12,2,8,1,4]. Como você pode ver na matriz, o elemento raiz está violando a prioridade Min Heap. Para manter a propriedade Min heap, você deve executar as operações min-heapify para trocar os elementos até que as propriedades Min heap sejam atendidas.

Pilha Máxima

Na estrutura do Max Heap, o nó pai ou raiz tem um valor igual ou maior que seus filhos no nó. Este nó contém o valor máximo. Além disso, é uma árvore binária completa, então você pode construir um heap máximo a partir de uma coleção de valores e executá-lo em tempo O(n).

Aqui estão alguns métodos para implementar um heap java max

Adicionar (): coloque um novo elemento em uma pilha. Se você usar um array, os objetos serão adicionados no final do array, enquanto na árvore binária, os objetos serão adicionados de cima para baixo e depois da esquerda para a direita.
Remover (): Este método permite remover o primeiro elemento da lista do array. Como o elemento recém-adicionado não é mais o maior, o método Sift-Down sempre o empurra para seu novo local.
Peneirar (): este método compara um objeto raiz com seu filho e, em seguida, empurra o nó recém-adicionado para sua posição correta.
Peneirar (): se você usar o método array para adicionar um elemento recém-inserido a um array, o método Sift-Up ajudará o nó recém-adicionado a se mudar para sua nova posição. O item recém-inserido é primeiro comparado ao pai, simulando a estrutura de dados em árvore.
Aplique a fórmula Parent_Index=Child_Index/2. Você continua fazendo isso até que o elemento máximo esteja na frente do array.

Pilha Básica Operações

Para encontrar os valores mais altos e mais baixos em um conjunto de dados, você precisa de muitas operações básicas de heap, como localizar, excluir e inserir. Como os elementos irão e virão constantemente, você deve:

Encontre – Procure um item em uma pilha.
inserção – Adicione um novo filho ao heap.
Apagar – Exclua um nó de um heap.

Criar pilhas

O processo de construção de heaps é conhecido como criação de heaps. Dada uma lista de chaves, o programador cria um heap vazio e depois insere outras chaves, uma de cada vez, usando operações básicas de heap.

Então, vamos começar a construir um heap mínimo usando o método de Willaim, inserindo os valores 12,2,8,1 e 4 em um heap. Você pode construir o heap com n elementos começando com um heap vazio e depois preenchendo-o sucessivamente com outros elementos usando o tempo O (nlogn).

Heapify: no algoritmo de inserção, que ajuda a inserir elementos em um heap. Verificações se a estrutura de dados do heap de propriedade destacada são seguidas.
Por exemplo, um heapify máximo verificaria se o valor do pai é maior que o de seu filho. Os elementos podem então ser classificados usando métodos como troca.

Mesclar: Considerando que você tem dois heaps para combinar em um, use mesclar heaps para reunir os valores dos dois heaps. No entanto, os montes originais ainda estão preservados.

Inspecionar pilhas

Inspecionar Heaps refere-se à verificação do número de elementos na estrutura de dados do heap e à validação se o heap está vazio.

É importante inspecionar heaps como classificação ou enfileiramento de elementos. É importante verificar se você tem elementos para processar usando Is-Empty(). O tamanho do heap ajudará a localizar o heap máximo ou o heap mínimo. Então, você precisa conhecer os elementos que seguem a propriedade heap.

Tamanho – retorna a magnitude ou comprimento do heap. Você pode dizer quantos elementos estão em ordem de classificação.
Está vazia – se o heap for NULL, retorna TRUE, caso contrário, retorna FALSE.

Aqui, você está imprimindo todos os elementos do prioridadeQ loop e, em seguida, verificando se a prioridadeQ não está vazia.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Usos da estrutura de dados heap

A estrutura de dados heap é útil em muitos aplicativos de programação na vida real, como:

Ajuda na filtragem de spam.
Implementando algoritmos gráficos.
Operabalanceamento de carga do sistema e compactação de dados.
Encontre a ordem nas estatísticas.
Implemente filas prioritárias onde você pode pesquisar itens em uma lista em tempo logarítmico.
A estrutura de dados heap também é usada para classificação.
Simulando clientes em uma linha.
Tratamento de interrupções em Sistema Operacional.
Na codificação de Huffman para compressão de dados.

Propriedades da fila de prioridade de heap

Nos heaps de prioridade, os itens de dados na lista são comparados entre si para determinar o elemento menor.
Um elemento é colocado em uma fila e posteriormente removido.
Cada elemento da Fila de Prioridade possui um número exclusivo relacionado a ele, identificado como prioritário.
Ao sair de uma fila de prioridade, o elemento de prioridade superior sai primeiro.

Etapas para implementar a fila de prioridade de heap em Java

Heap Sort em JAVA com exemplo de código

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

saída

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Classificação de pilha Python com exemplo de código

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)