Estrutura de dados Heap: O que é um Heap?

O que é uma estrutura de dados Heap?

Uma Heap é uma estrutura de dados especializada baseada em árvore. A estrutura de dados Heap compreende um nó superior chamado raiz (pai). Seu segundo nó é o filho esquerdo da raiz, enquanto o terceiro nó é o filho direito da raiz. Os nós subsequentes são preenchidos da esquerda para a direita. A chave do nó pai é comparada à de seus filhos para que ocorra um arranjo adequado. A árvore é fácil de visualizar, onde cada entidade é chamada de nó e cada nó possui uma chave única para identificação.

Em termos simples, um Heap é uma árvore binária completa que satisfaz a propriedade de heap: cada elemento pai é ordenado de forma consistente em relação aos seus filhos, o que o torna ideal para filas de prioridade e para o algoritmo de ordenação por heap (Heap Sort).

Por que você precisa da estrutura de dados Heap?

Aqui estão os principais motivos para usar um Heap:

• A estrutura de dados Heap permite a remoção e inserção em tempo logarítmico – O(log n).₂não).
• Os dados na árvore são organizados em uma ordem específica. Além de atualizar ou consultar valores como máximo ou mínimo, o programador pode encontrar relações entre o elemento pai e os elementos filhos.
• Você pode aplicar o conceito de Modelo de Objeto de Documento Para ajudar você a entender visualmente a estrutura de dados Heap.
• As heaps suportam operações eficientes de filas de prioridade, que são cruciais para algoritmos de grafos como o caminho mais curto de Dijkstra e a árvore geradora mínima de Prim.

Tipos de pilhas

A estrutura de dados Heap possui vários algoritmos para lidar com inserções e remoções de elementos, incluindo Fila de Prioridade, Heap Binário, Heap Binomial e Classificação de pilha.

• Fila de prioridade: É um abdômentracUma estrutura de dados contendo objetos priorizados. Cada objeto ou item possui uma prioridade predefinida. Portanto, o objeto ou item com a maior prioridade recebe o serviço antes dos demais.
• Heap binário: Heaps binários são adequados para operações simples de heap, como remoções e inserções. Eles são a implementação padrão por trás da maioria das filas de prioridade da biblioteca padrão.
• Heap binomial: Uma Heap Binomial consiste em uma série de coleções de árvores binomiais que compõem a heap. Uma árvore de Heap Binomial não é uma árvore comum, pois é rigorosamente definida. O número total de elementos em uma árvore binomial é sempre igual a 2ⁿ.ⁿ nós.
• Ordenação por Heap: Ao contrário da maioria dos algoritmos de ordenação, o Heap Sort utiliza espaço O(1) para sua operação de ordenação. É um algoritmo de ordenação baseado em comparação, onde a ordenação ocorre em ordem crescente, transformando primeiro a entrada em um Max-Heap. Você pode considerar o Heap Sort como uma árvore de busca binária aprimorada.

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

• Pilha mínima – menor valor no topo
• Pilha Máxima – valor mais alto no topo

Pilha mínima

Na estrutura Min-Heap, o nó raiz possui um valor igual ou menor que o de seus filhos. Portanto, a raiz de um Min-Heap contém o valor mínimo. O Min-Heap também é uma árvore binária completa.

Uma vez que você tenha um Min-Heap em uma árvore, todas as folhas são candidatas viáveis ​​para o valor máximo. No entanto, você precisa examinar cada folha para obter o valor exato do Max-Heap.

Exemplo de Min-Heap

No diagrama acima, você pode observar uma sequência clara da raiz até o nó mais baixo.

Suponha que você armazene os elementos no array Array_N[12, 2, 8, 1, 4]. Como você pode ver no array, o elemento raiz está violando a prioridade do Min-Heap. Para manter a propriedade Min-Heap, você precisa realizar as operações de min-heapificação para trocar os elementos de lugar até que as regras do Min-Heap sejam atendidas.

Pilha Máxima

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

Aqui estão alguns métodos comumente usados ​​na implementação de um Java Heap máximo:

• Adicionar (): Adiciona um novo elemento a um heap. Se você usar um array, os objetos são adicionados ao final do array, enquanto em uma árvore binária, os objetos são adicionados de cima para baixo e depois da esquerda para a direita.
• Remover (): Este método permite remover o primeiro elemento da lista de arrays. Como o elemento recém-promovido não é mais o maior, o método Sift-Down sempre o move para sua nova posição.
• Peneirar para baixo (): Este método compara um objeto raiz com seus filhos e, em seguida, move o nó realocado para sua posição correta.
• Peneirar (): Se você usar o método de array para adicionar um novo elemento a um array, o método Sift-Up ajudará o nó recém-adicionado a se realocar para a posição correta. O novo item é comparado primeiro ao seu elemento pai, simulando a estrutura de dados em árvore.

  Aplique a fórmula Índice_Pai = Índice_Filho / 2. Continue fazendo isso até que o elemento máximo esteja no início da matriz.

Pilha Básica Operações

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

• 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, em seguida, insere as outras chaves uma de cada vez usando as operações básicas de heap.

Vamos então começar a construir um Min-Heap usando o método de William, inserindo os valores 12, 2, 8, 1 e 4. Você pode construir o heap com n elementos começando com um heap vazio e preenchendo-o sucessivamente com outros elementos usando um tempo O(n log n).

• Heapify: Uma rotina de inserção que ajuda a inserir elementos em um heap, preservando as propriedades do heap.

  Por exemplo, uma operação de max-heapify verifica se o valor do elemento pai é maior que o do elemento filho. Os elementos podem então ser ordenados usando métodos como swap.ping.

• Mesclar: Quando você precisa combinar dois heaps em um só, use a operação de mesclagem para reunir os valores dos dois heaps. Os heaps originais são preservados.

Inspecionar pilhas

Inspecionar heaps significa verificar o número de elementos na estrutura de dados Heap e validar se o heap está vazio.

É importante inspecionar os heaps durante a ordenação ou enfileiramento de elementos. Verificar se há elementos para processar usando `Is-Empty()` é fundamental. O tamanho do heap ajudará a localizar as raízes do Max-Heap ou do Min-Heap, portanto, é necessário saber quantos elementos seguem a propriedade do heap.

• Dimensões: – Retorna a magnitude ou o comprimento do heap. Indica quantos elementos estão armazenados em ordem classificada.
• Está vazio – retorna VERDADEIRO se o heap for nulo, caso contrário retorna FALSO.

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 muitas aplicações de programação na vida real, tais como:

• Auxilia na filtragem de spam.
• Implementação de algoritmos de grafos como Dijkstra e Prim.
• Operabalanceamento de carga do sistema e compressão de dados.
• Encontrar estatísticas de ordem, como o k-ésimo menor elemento.
• Implementação de filas de prioridade onde é possível pesquisar itens em uma lista em tempo logarítmico.
• A estrutura de dados Heap também é usada para ordenação através do Heap Sort.
• Simulação de clientes em uma fila de espera.
• Tratamento de interrupções no Sistema Operacional.
• Na codificação de Huffman para compressão de dados.
• Aprimorando a busca em largura e as heurísticas A* no planejamento de trajetórias em IA.

Propriedades da fila de prioridade de heap

As propriedades a seguir descrevem o comportamento da fila de prioridade construída sobre um heap:

• Em heaps de prioridade, os itens de dados na lista são comparados entre si para determinar o elemento menor ou maior.
• Um elemento é colocado em uma fila e, posteriormente, removido por ordem de prioridade.
• Cada elemento na fila de prioridade possui um número único associado a ele, que o identifica como sua prioridade.
• Ao sair de uma fila de prioridade, o elemento de maior prioridade sai primeiro.

Passos para implementar a fila de prioridade Heap em Java

A próxima seção aborda o concreto. Java Implementação que transforma essas regras em código funcional.

Classificação de pilha Java com as Code Exemplo

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 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 as Code Exemplo

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)

saída

[1, 3, 4, 7, 9]

Em seguida, você aprenderá sobre o Método de bissecção.

Perguntas Frequentes