Guia para heaps em Python

Introdução

Imagine um aeroporto movimentado com voos decolando e pousando a cada minuto. Assim como os controladores de tráfego aéreo priorizam os voos com base na urgência, os heaps nos ajudam a gerenciar e processar dados com base em critérios específicos, garantindo que os dados mais “urgentes” ou “importantes” estejam sempre acessíveis no topo.

Neste guia, embarcaremos em uma jornada para entender os montes desde o início. Começaremos desmistificando o que são heaps e suas propriedades inerentes. A partir daí, mergulharemos na implementação de heaps do próprio Python, o heapq módulo e explore seu rico conjunto de funcionalidades. Portanto, se você já se perguntou como gerenciar com eficiência um conjunto dinâmico de dados onde o elemento de prioridade mais alta (ou mais baixa) é frequentemente necessário, você terá uma surpresa.

O que é uma pilha?

A primeira coisa que você gostaria de entender antes de mergulhar no uso de heaps é o que é um monte. Um heap se destaca no mundo das estruturas de dados como uma potência baseada em árvore, particularmente hábil em mantendo a ordem e a hierarquia. Embora possa parecer uma árvore binária para olhos destreinados, as nuances em sua estrutura e regras que a governam o diferenciam claramente.

Uma das características que definem um heap é a sua natureza como um árvore binária completa. Isto significa que todos os níveis da árvore, exceto talvez o último, estão totalmente preenchidos. Neste último nível, os nós são preenchidos da esquerda para a direita. Tal estrutura garante que os heaps possam ser representados e manipulados de forma eficiente usando arrays ou listas, com a posição de cada elemento no array refletindo seu posicionamento na árvore.

A verdadeira essência de uma pilha, no entanto, reside na sua ordenação. Num pilha máxima, o valor de qualquer nó ultrapassa ou iguala os valores de seus filhos, posicionando o maior elemento logo na raiz. Por outro lado, um pilha mínima opera no princípio oposto: o valor de qualquer nó é menor ou igual aos valores de seus filhos, garantindo que o menor elemento fique na raiz.

À medida que avançamos, nos aprofundaremos em como essas propriedades inerentes aos heaps permitem operações eficientes e como as funções do Python heapq O módulo integra perfeitamente montes em nossos esforços de codificação.

Características e propriedades dos montes

Heaps, com sua estrutura única e princípios de ordenação, trazem um conjunto de características e propriedades distintas que os tornam inestimáveis ​​em vários cenários computacionais.

Em primeiro lugar, os montes são inerentemente eficiente. Sua estrutura baseada em árvore, especificamente o formato de árvore binária completa, garante que operações como inserção e extração de elementos prioritários (máximo ou mínimo) possam ser realizadas em tempo logarítmico, normalmente O (log n). Essa eficiência é uma vantagem para algoritmos e aplicações que exigem acesso frequente a elementos prioritários.

Outra propriedade notável dos heaps é a sua eficiência de memória. Como os heaps podem ser representados usando matrizes ou listas sem a necessidade de ponteiros explícitos para nós filhos ou pais, eles economizam espaço. A posição de cada elemento na matriz corresponde ao seu posicionamento na árvore, permitindo travessia e manipulação previsíveis e diretas.

A propriedade de ordenação dos heaps, seja como heap máximo ou heap mínimo, garante que a raiz sempre contém o elemento de maior prioridade. Essa ordenação consistente é o que permite acesso rápido ao elemento de maior prioridade sem a necessidade de pesquisar em toda a estrutura.

Além disso, os montes são versátil. Embora os heaps binários (onde cada pai tem no máximo dois filhos) sejam os mais comuns, os heaps podem ser generalizados para ter mais de dois filhos, conhecidos como montes d-ários. Essa flexibilidade permite o ajuste fino com base em casos de uso e requisitos de desempenho específicos.

Por último, os montes são auto-ajustável. Sempre que elementos são adicionados ou removidos, a estrutura se reorganiza para manter suas propriedades. Esse balanceamento dinâmico garante que o heap permaneça sempre otimizado para suas operações principais.

À medida que nos aprofundamos na implementação e nas aplicações práticas do Python, o verdadeiro potencial dos heaps se revelará diante de nós.

Tipos de pilhas

Nem todos os heaps são criados iguais. Dependendo da sua ordenação e propriedades estruturais, as pilhas podem ser categorizadas em diferentes tipos, cada uma com o seu próprio conjunto de aplicações e vantagens. As duas categorias principais são pilha máxima e pilha mínima.

A característica mais marcante de um pilha máxima é que o valor de qualquer nó é maior ou igual aos valores de seus filhos. Isso garante que o maior elemento do heap sempre resida na raiz. Tal estrutura é particularmente útil quando há necessidade de acessar frequentemente o elemento máximo, como em certas implementações de filas prioritárias.

A contrapartida do heap máximo, um pilha mínima garante que o valor de qualquer nó seja menor ou igual aos valores de seus filhos. Isso posiciona o menor elemento do heap na raiz. Os heaps mínimos são inestimáveis ​​em cenários onde o menor elemento é de primordial importância, como em algoritmos que lidam com processamento de dados em tempo real.

Além dessas categorias primárias, os heaps também podem ser distinguidos com base no seu fator de ramificação:

Embora os heaps binários sejam os mais comuns, com cada pai tendo no máximo dois filhos, o conceito de heaps pode ser estendido a nós com mais de dois filhos. Em um pilha d-ária, cada nó tem no máximo d crianças. Essa variação pode ser otimizada para cenários específicos, como diminuir a altura da árvore para agilizar determinadas operações.

Pilha Binomial é um conjunto de árvores binomiais definidas recursivamente. Heaps binomiais são usados ​​em implementações de filas prioritárias e oferecem operações de mesclagem eficientes.

Nomeado após a famosa sequência de Fibonacci, o pilha de Fibonacci oferece tempos de execução melhor amortizados para muitas operações em comparação com heaps binários ou binomiais. Eles são particularmente úteis em algoritmos de otimização de rede.

Implementação de Heap do Python – O pilha Módulo

Python oferece um módulo integrado para operações heap – o heapq módulo. Este módulo fornece uma coleção de funções relacionadas ao heap que permitem aos desenvolvedores transformar listas em heaps e executar várias operações de heap sem a necessidade de uma implementação customizada. Vamos mergulhar nas nuances deste módulo e como ele traz a você o poder dos montes.

A heapq O módulo não fornece um tipo de dados de heap distinto. Em vez disso, oferece funções que funcionam em listas regulares do Python, transformando-as e tratando-as como pilhas binárias.

Essa abordagem economiza memória e se integra perfeitamente às estruturas de dados existentes do Python.

Isso significa que heaps são representados como listas in heapq. A beleza desta representação é a sua simplicidade – o sistema de índice de lista baseado em zero serve como uma árvore binária implícita. Para qualquer elemento na posição i, Está:

• A criança esquerda está na posição 2*i + 1
• A criança certa está na posição 2*i + 2
• O nó pai está na posição (i-1)//2

Essa estrutura implícita garante que não haja necessidade de uma representação de árvore binária separada baseada em nós, tornando as operações simples e o uso de memória mínimo.

É essencial notar que o heapq módulo cria min heaps por padrão. Isso significa que o menor elemento está sempre na raiz (ou na primeira posição da lista). Se você precisar de um heap máximo, terá que inverter a ordem multiplicando os elementos por -1 ou use uma função de comparação personalizada.

Python's heapq O módulo fornece um conjunto de funções que permite aos desenvolvedores realizar várias operações de heap em listas.

Nas seções a seguir, nos aprofundaremos em cada uma dessas operações fundamentais, explorando sua mecânica e casos de uso.

Como transformar uma lista em um heap

A heapify() function é o ponto de partida para muitas tarefas relacionadas ao heap. É necessário um iterável (normalmente uma lista) e reorganiza seus elementos no local para satisfazer as propriedades de um heap mínimo:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Isso gerará uma lista reordenada que representa um heap mínimo válido:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Como adicionar um elemento ao heap

A heappush() A função permite inserir um novo elemento no heap enquanto mantém as propriedades do heap:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

A execução do código fornecerá uma lista de elementos que mantêm a propriedade min heap:

[3, 5, 7]

Como remover e retornar o menor elemento da pilha

A heappop() A função extrai e retorna o menor elemento do heap (a raiz em um heap mínimo). Após a remoção, garante que a lista permaneça um heap válido:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Isso produzirá o menor elemento e a lista restante:

1
[3, 7, 5, 9]

Aqui, 1 é o menor elemento do heap, e a lista restante manteve a propriedade heap, mesmo depois de removermos 1.

Como enviar um novo item e abrir o menor item

A heappushpop() função é uma operação combinada que coloca um novo item no heap e, em seguida, exibe e retorna o menor item do heap:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Isto irá produzir 3, o menor elemento, e imprima o novo heap lista que agora inclui 4 enquanto mantém a propriedade heap:

3
[4, 5, 7, 9]

Como substituir o menor item e enviar um novo item

A heapreplace() função exibe o menor elemento e coloca um novo elemento no heap, tudo em uma operação eficiente:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Isto imprime 1, o menor elemento, e a lista agora inclui 4 e mantém a propriedade heap:

1
[4, 5, 7, 9]

Encontrando vários extremos no heap do Python

nlargest(n, iterable[, key]) e nsmallest(n, iterable[, key]) funções são projetadas para recuperar vários elementos maiores ou menores de um iterável. Eles podem ser mais eficientes do que classificar todo o iterável quando você precisa apenas de alguns valores extremos. Por exemplo, digamos que você tenha a lista a seguir e queira encontrar três valores menores e três maiores na lista:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Aqui, nlargest() e nsmallest() funções podem ser úteis:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Isto lhe dará duas listas – uma contém os três maiores valores e a outra contém os três menores valores do data Lista:

[9, 6, 5]
[1, 1, 2]

Como construir seu heap personalizado

Enquanto o Python heapq fornece um conjunto robusto de ferramentas para trabalhar com heaps, há cenários em que o comportamento padrão de min heap pode não ser suficiente. Se você deseja implementar um heap máximo ou precisa de um heap que opere com base em funções de comparação customizadas, construir um heap customizado pode ser a resposta. Vamos explorar como adaptar pilhas às necessidades específicas.

Implementando um Max Heap usando heapq

Por padrão, o heapq cria min pilhas. No entanto, com um truque simples, você pode usá-lo para implementar um heap máximo. A ideia é inverter a ordem dos elementos multiplicando-os por -1 antes de adicioná-los ao heap:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Com esta abordagem, o maior número (em termos de valor absoluto) torna-se o menor, permitindo que o heapq funções para manter uma estrutura de heap máximo.

Heaps com funções de comparação personalizadas

Às vezes, você pode precisar de um heap que não compare apenas com base na ordem natural dos elementos. Por exemplo, se você estiver trabalhando com objetos complexos ou tiver critérios de classificação específicos, uma função de comparação personalizada torna-se essencial.

Para conseguir isso, você pode agrupar elementos em uma classe auxiliar que substitui os operadores de comparação:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Com esta configuração, você pode definir qualquer função de comparação personalizada e usá-la com o heap.

Conclusão

Os heaps oferecem desempenho previsível para muitas operações, tornando-os uma escolha confiável para tarefas baseadas em prioridades. No entanto, é essencial considerar os requisitos e características específicas da aplicação em questão. Em alguns casos, ajustar a implementação do heap ou até mesmo optar por estruturas de dados alternativas pode produzir um melhor desempenho no mundo real.

Os montes, como vimos, são mais do que apenas mais uma estrutura de dados. Eles representam uma confluência de eficiência, estrutura e adaptabilidade. Desde suas propriedades fundamentais até sua implementação em Python heapq módulo, os heaps oferecem uma solução robusta para uma infinidade de desafios computacionais, especialmente aqueles centrados na prioridade.

• Conteúdo com tecnologia de SEO e distribuição de relações públicas. Seja amplificado hoje.
• PlatoData.Network Gerativa Vertical Ai. Capacite-se. Acesse aqui.
• PlatoAiStream. Inteligência Web3. Conhecimento Amplificado. Acesse aqui.
• PlatãoESG. Carbono Tecnologia Limpa, Energia, Ambiente, Solar, Gestão de resíduos. Acesse aqui.
• PlatoHealth. Inteligência em Biotecnologia e Ensaios Clínicos. Acesse aqui.
• Fonte: https://stackabuse.com/guide-to-heaps-in-python/