Heap vs Árvore de pesquisa binária (BST)

169

Qual é a diferença entre um heap e BST?

Quando usar uma pilha e quando usar uma BST?

Se você deseja obter os elementos de maneira ordenada, o BST é melhor do que o heap?

kc3
fonte
13
Esta questão parece ser off-topic porque se trata de ciência da computação e devem ser feitas em cs.stackexchange.com
Fluxo
3
@Flow, foi perguntado lá em: cs.stackexchange.com/questions/27860/…
Ciro Santilli 郝海东 郝海东 病 六四 事件
3
Eu sinto que isso se relaciona com a troca de pilha e o estouro de pilha. Então, tê-lo aqui é bom #
1111 Azizbro

Respostas:

191

Resumo

          Type      BST (*)   Heap
Insert    average   log(n)    1
Insert    worst     log(n)    log(n) or n (***)
Find any  worst     log(n)    n
Find max  worst     1 (**)    1
Create    worst     n log(n)  n
Delete    worst     log(n)    log(n)

Todos os tempos médios nesta tabela são iguais aos piores, exceto para Inserir.

  • *: em toda parte nesta resposta, BST == BST balanceado, pois o desbalanceado é uma droga assintoticamente
  • **: usando uma modificação trivial explicada nesta resposta
  • ***: log(n)para heap de árvore de ponteiro, npara heap de matriz dinâmica

Vantagens da pilha binária sobre uma BST

  • o tempo médio de inserção em uma pilha binária é O(1), para BST, é O(log(n)). Este é o recurso matador de pilhas.

    Também existem outros montes que atingem O(1)amortizados (mais fortes) como o Fibonacci Heap e, pior ainda, como a fila Brodal , embora possam não ser práticos por causa do desempenho não assintótico: Os montes Fibonacci ou as filas Brodal são usados ​​na prática em algum lugar?

  • pilhas binárias podem ser implementadas com eficiência em cima de matrizes dinâmicas ou em árvores baseadas em ponteiro, e apenas em árvores baseadas em ponteiro do BST. Portanto, para o heap, podemos escolher a implementação de array com mais espaço, se pudermos permitir latências de redimensionamento ocasionais.

  • a criação de heap binária é o O(n)pior caso , O(n log(n))para o BST.

Vantagem do BST sobre heap binário

  • procurar por elementos arbitrários é O(log(n)). Esse é o recurso matador dos BSTs.

    Para heap, O(n)geralmente é, exceto o maior elemento que é O(1).

Vantagem "falsa" do heap sobre o BST

  • heap é O(1)encontrar max, BST O(log(n)).

    Esse é um equívoco comum, porque é trivial modificar uma BST para rastrear o maior elemento e atualizá-lo sempre que esse elemento puder ser alterado: na inserção de uma troca maior, na remoção, encontre a segunda maior. Podemos usar a árvore de pesquisa binária para simular a operação de heap? (mencionado por Yeo ).

    Na verdade, essa é uma limitação de pilhas em comparação com as BSTs: a única pesquisa eficiente é a do maior elemento.

A inserção média de heap binário é O(1)

Fontes:

Argumento intuitivo:

  • os níveis das árvores inferiores têm exponencialmente mais elementos do que os níveis superiores; portanto, é quase certo que novos elementos vão para o fundo
  • a inserção da pilha começa na parte inferior , a BST deve começar na parte superior

Em uma pilha binária, aumentar o valor em um determinado índice também é O(1)pelo mesmo motivo. Mas se você quiser fazer isso, é provável que deseje manter um índice extra atualizado sobre as operações de heap Como implementar a operação de chave de diminuição de O (logn) para a Fila de prioridades com base em min heap? por exemplo, para Dijkstra. Possível sem custo adicional.

Referência de inserção de biblioteca padrão da GCC C ++ em hardware real

Fiz um teste comparativo das inserções C ++ std::set( Red-black tree BST ) e std::priority_queue( dynamic array heap ) para ver se eu estava certo sobre os tempos de inserção, e foi isso que obtive:

insira a descrição da imagem aqui

  • código de referência
  • roteiro
  • dados de plotagem
  • testado no Ubuntu 19.04, GCC 8.3.0 em um laptop Lenovo ThinkPad P51 com CPU: CPU Intel Core i7-7820HQ (4 núcleos / 8 threads, base de 2,90 GHz, cache de 8 MB), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB , 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

Tão claramente:

  • o tempo de inserção da pilha é basicamente constante.

    Podemos ver claramente os pontos de redimensionamento da matriz dinâmica. Como estamos calculando a média de cada 10k inserções para poder ver qualquer coisa acima do ruído do sistema , esses picos são de fato cerca de 10k vezes maiores do que os mostrados!

    O gráfico ampliado exclui essencialmente apenas os pontos de redimensionamento da matriz e mostra que quase todas as inserções ficam abaixo de 25 nanossegundos.

  • O BST é logarítmico. Todas as inserções são muito mais lentas que a inserção de pilha média.

  • Análise detalhada de BST vs hashmap em: Qual estrutura de dados está dentro de std :: map em C ++?

Referência de inserção de biblioteca padrão GCC C ++ na gem5

gem5 é um simulador de sistema completo e, portanto, fornece um relógio infinitamente preciso com m5 dumpstats. Então, tentei usá-lo para estimar tempos para inserções individuais.

insira a descrição da imagem aqui

Interpretação:

  • o heap ainda é constante, mas agora vemos com mais detalhes que existem algumas linhas e cada linha superior é mais esparsa.

    Isso deve corresponder à latência de acesso à memória para inserções cada vez mais altas.

  • TODO Eu realmente não consigo interpretar completamente o BST, pois ele não parece tão logarítmico e um pouco mais constante.

    Com esse detalhe maior, no entanto, podemos ver também algumas linhas distintas, mas não tenho certeza do que elas representam: eu esperaria que a linha inferior fosse mais fina, pois inserimos a parte inferior superior?

Comparado com esta configuração do Buildroot em uma CPU HPI aarch64 .

O BST não pode ser implementado com eficiência em uma matriz

As operações de heap precisam apenas subir ou descer um único galho de árvore, de modo O(log(n))que as trocas de pior caso, em O(1)média.

Manter um BST equilibrado requer rotações em árvore, o que pode alterar o elemento superior para outro e exigiria a movimentação de toda a matriz ( O(n)).

As pilhas podem ser implementadas eficientemente em uma matriz

Os índices pai e filho podem ser calculados a partir do índice atual, como mostrado aqui .

Não há operações de balanceamento como o BST.

Excluir min é a operação mais preocupante, pois precisa ser descendente. Mas isso sempre pode ser feito "percolando" um único ramo da pilha, conforme explicado aqui . Isso leva ao pior caso de O (log (n)), pois o heap é sempre bem equilibrado.

Se você estiver inserindo um único nó para cada um que remover, perderá a vantagem da inserção média assintótica O (1) fornecida pelos montões, pois a exclusão dominaria, e é melhor usar uma BST. No entanto, o Dijkstra atualiza os nós várias vezes para cada remoção, por isso estamos bem.

Heaps de matriz dinâmica x heap de árvore de ponteiro

As pilhas podem ser implementadas com eficiência em cima das pilhas de ponteiro: É possível fazer implementações eficientes de pilha binária baseada em ponteiro?

A implementação do array dinâmico é mais eficiente em espaço. Suponha que cada elemento de heap contenha apenas um ponteiro para um struct:

  • a implementação em árvore deve armazenar três ponteiros para cada elemento: pai, filho esquerdo e filho direito. Portanto, o uso da memória é sempre 4n(3 ponteiros de árvore + 1 structponteiro).

    Os BSTs em árvore também precisariam de mais informações de balanceamento, por exemplo, preto-vermelho-ness.

  • a implementação do array dinâmico pode ter tamanho 2nlogo após uma duplicação. Então, em média, será 1.5n.

Por outro lado, o heap da árvore tem a melhor inserção de pior caso, porque copiar o array dinâmico de backup para dobrar seu tamanho é o O(n)pior caso, enquanto o heap da árvore faz novas alocações pequenas para cada nó.

Ainda assim, a duplicação da matriz de apoio é O(1)amortizada, reduzindo-se a uma consideração de latência máxima. Mencionado aqui .

Filosofia

  • As BSTs mantêm uma propriedade global entre um pai e todos os descendentes (menor à esquerda, maior à direita).

    O nó superior de uma BST é o elemento do meio, que requer conhecimento global para manter (sabendo quantos elementos menores e maiores existem).

    Essa propriedade global é mais cara de manter (log n insert), mas fornece pesquisas mais poderosas (log n search).

  • As pilhas mantêm uma propriedade local entre pais e filhos diretos (pai> filhos).

    O nó superior de um heap é o grande elemento, que requer apenas o conhecimento local para manter (conhecer seu pai).

Comparando BST vs Heap vs Hashmap:

  • BST: pode ser razoável:

    • conjunto não ordenado (uma estrutura que determina se um elemento foi inserido ou não anteriormente). Mas o hashmap tende a ser melhor devido ao O (1) inserto amortizado.
    • máquina de triagem. Mas o heap geralmente é melhor nisso, e é por isso que o heapsort é muito mais conhecido do que o tipo de árvore
  • heap: é apenas uma máquina de classificação. Não pode ser um conjunto não ordenado eficiente, porque você só pode verificar o elemento menor / maior rapidamente.

  • mapa de hash: só pode ser um conjunto não ordenado, não uma máquina de classificação eficiente, porque o hash mistura qualquer pedido.

Lista duplamente vinculada

Uma lista duplamente vinculada pode ser vista como subconjunto da pilha em que o primeiro item tem maior prioridade, então vamos compará-los aqui também:

  • inserção:
    • posição:
      • lista duplamente vinculada: o item inserido deve ser o primeiro ou o último, pois só temos ponteiros para esses elementos.
      • pilha binária: o item inserido pode terminar em qualquer posição. Menos restritivo que a lista vinculada.
    • Tempo:
      • lista duplamente vinculada: na O(1)pior das hipóteses, pois temos ponteiros para os itens e a atualização é realmente simples
      • pilha binária: O(1)média, pior que a lista vinculada. Troca por ter uma posição de inserção mais geral.
  • pesquisa: O(n)para ambos

Um caso de uso para isso é quando a chave do heap é o carimbo de data / hora atual: nesse caso, novas entradas sempre irão para o início da lista. Assim, podemos até esquecer completamente o registro de data e hora exato e manter a posição na lista como a prioridade.

Isso pode ser usado para implementar um cache LRU . Assim como em aplicativos de heap como o Dijkstra , você deseja manter um mapa de hash adicional da chave no nó correspondente da lista, para descobrir qual nó atualizar rapidamente.

Comparação de diferentes BST Balanceados

Embora a inserção assintótica e os tempos de localização de todas as estruturas de dados classificadas como "BSTs balanceadas" que eu vi até agora sejam os mesmos, BBSTs diferentes têm compensações diferentes. Ainda não estudei completamente isso, mas seria bom resumir essas trocas aqui:

  • Árvore vermelho-preta . Parece ser o BBST mais usado a partir de 2019, por exemplo, é o usado pela implementação do GCC 8.3.0 C ++
  • Árvore AVL . Parece ser um pouco mais equilibrado que o BST, portanto, seria melhor encontrar latência, ao custo de descobertas um pouco mais caras. O Wiki resume: "As árvores AVL são frequentemente comparadas com as árvores vermelho-preto porque ambas suportam o mesmo conjunto de operações e demoram [o mesmo] tempo para as operações básicas. Para aplicativos que exigem muita pesquisa, as árvores AVL são mais rápidas que as árvores vermelho-preto porque elas são mais estritamente equilibradas.Como as árvores vermelho-pretas, as árvores AVL são equilibradas em altura.Em geral, ambas não são balanceadas em peso nem mu para qualquer mu <1/2; ou seja, os nós irmãos podem ter um enorme números diferentes de descendentes ".
  • WAVL . O artigo original menciona vantagens dessa versão em termos de limites nas operações de reequilíbrio e rotação.

Veja também

Pergunta semelhante no CS: /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

Ciro Santilli adicionou uma nova foto
fonte
4
Marcado com +1, mas o "papel" que justifica a inserção de heap binária média de O (1) agora é um link morto e os "slides" apenas declaram a reivindicação sem prova. Também acho que ajudaria a esclarecer que "caso médio" aqui significa a média assumindo que os valores inseridos vêm de alguma distribuição específica , então não tenho certeza de quão "matador" esse recurso realmente é.
Jrandom_hacker 16/09/16
3
O BST e o BST equilibrado parecem ser usados ​​de forma intercambiável. Deve ficar claro que a resposta se refere a BST equilibrado para evitar confusão.
gkalpak
2
@Bulat Sinto que estamos nos desviando um pouco, mas se quisermos max e min ao mesmo tempo, poderemos ter problemas com a manutenção de dois montões se não tomarmos cuidado - stackoverflow.com/a/1098454/7154924 . Provavelmente é melhor usar um heap max-min (devido a Atkinson et al.), Que é projetado especificamente para esse fim.
flow2k
1
@CiroSantilli 法轮功 改造 中心 六四 事件: Não entendo por que a operação de exclusão de um heap binário é O (log n). Isso funciona apenas se você tiver um ponteiro para o elemento no heap, mas na maioria dos casos de uso, você possui a chave e precisa localizar o elemento primeiro que recebe O (n).
Ricola
5
a inserção de heap é log (n) não o (1)
Bobo
78

O heap apenas garante que os elementos em níveis mais altos sejam maiores (para max-heap) ou menores (para min-heap) do que os elementos em níveis mais baixos, enquanto o BST garante a ordem (da "esquerda" para a "direita"). Se você deseja classificar elementos, vá com o BST.

Código Dante May
fonte
8
"O heap apenas garante que os elementos em níveis mais altos sejam maiores (para max-heap) ou menores (para min-heap) que os elementos em níveis mais baixos, ..." - o heap não impõe isso por nível , mas apenas em pai-filho- correntes. [1, 5, 9, 7, 15, 10, 11]representa um min-heap válido, mas o 7nível 3 é menor que o 9nível 2. Para uma visualização, consulte, por exemplo, os elementos 25e 19na imagem de exemplo da Wikipedia para heaps . (Note também que as relações de desigualdade entre os elementos não são rigorosos, já que os elementos não são necessariamente exclusivos.)
Daniel Andersson
Desculpe pela entrada tardia, mas eu só quero obter clareza. Se a pilha binária for classificada, o pior caso de pesquisa seria log n right. Portanto, nesse caso, as pilhas binárias são classificadas melhor que as árvores de pesquisa binária (BST vermelho-preto). Obrigado
Krishna
50

Quando usar um heap e quando usar um BST

O heap é melhor em findMin / findMax ( O(1)), enquanto o BST é bom em todos os resultados ( O(logN)). A inserção é O(logN)para ambas as estruturas. Se você se preocupa apenas com findMin / findMax (por exemplo, relacionado a prioridades), vá com heap. Se você quiser tudo organizado, vá com o BST.

Os primeiros slides daqui explicam as coisas com muita clareza.

xysun
fonte
3
Enquanto a inserção é logarítmica para ambos, no pior dos casos, a inserção média da pilha leva tempo constante. (Uma vez que a maioria dos elementos existentes estão na parte inferior, na maioria dos casos um novo elemento terá apenas a borbulhar um ou dois níveis, se em tudo.)
johncip
1
@xysun Eu acho que o BST é melhor em findMin & findMax stackoverflow.com/a/27074221/764592 #
Yeo
2
@Yeo: Heap é melhor para findMin xor findMax. Se você precisar de ambos , o BST é melhor.
quer
1
Eu acho que isso é apenas um equívoco comum. Uma árvore binária pode ser facilmente modificada para encontrar min e max, como apontado por Yeo. Na verdade, isso é uma restrição do heap: a única descoberta eficiente é min ou max. A verdadeira vantagem da pilha é O (1) de inserção média como eu explicar: stackoverflow.com/a/29548834/895245
Ciro Santilli郝海东冠状病六四事件法轮功
1
A resposta de Ciro Santilli é muito melhor: stackoverflow.com/a/29548834/2873507
Vic Seedoubleyew,
9

Conforme mencionado por outros, o Heap pode fazer findMin ou findMax em O (1), mas não ambos na mesma estrutura de dados. No entanto, eu discordo que o Heap é melhor no findMin / findMax. De fato, com uma leve modificação, o BST pode fazer as duas coisas findMin e findMax em O (1).

Nesse BST modificado, você monitora o nó mínimo e o nó máximo toda vez que executa uma operação que pode potencialmente modificar a estrutura de dados. Por exemplo, na operação de inserção, é possível verificar se o valor mínimo é maior que o valor recém-inserido e atribuir o valor mínimo ao nó recém-adicionado. A mesma técnica pode ser aplicada no valor máximo. Portanto, este BST contém essas informações que você pode recuperá-las em O (1). (o mesmo que heap binário)

Nesta BST (BST balanceada), quando você pop minou pop max, o próximo valor mínimo a ser atribuído é o sucessor do nó mínimo, enquanto o próximo valor máximo a ser designado é o predecessor do nó máximo. Assim, ele executa em O (1). No entanto, precisamos reequilibrar a árvore, assim ela continuará executando O (log n). (o mesmo que heap binário)

Eu ficaria interessado em ouvir sua opinião no comentário abaixo. Obrigado :)

Atualizar

Referência cruzada a pergunta semelhante Podemos usar a árvore de pesquisa binária para simular a operação de heap? para mais discussões sobre a simulação do Heap usando o BST.

Yeo
fonte
Por que você discorda? você se importaria de compartilhar seu pensamento abaixo?
Yeo
Você certamente pode armazenar o valor máximo e / ou mínimo de um BST, mas o que acontece se você quiser exibi-lo? Você precisa pesquisar na árvore para removê-la e, em seguida, procurar novamente o novo máximo / min, ambos operações O (log n). Esse é o mesmo pedido das inserções e remoções em uma pilha prioritária, com uma constante pior.
Justin
@JustinLardinois Desculpe, esqueço de destacar isso na minha resposta. No BST, quando você pop min, o próximo valor min a ser atribuído é o sucessor do nó min. e se você exibir o valor máximo, o próximo valor máximo a ser atribuído é o predecessor do nó máximo. Assim, ele ainda atua em O (1).
Yeo
Correção: para popMinou popMaxnão é O (1), mas é O (log n) porque deve ser um BST balanceado que precisa ser reequilibrado a cada operação de exclusão. Por isso, o mesmo que montão binário popMinou popMaxque ó prazo (log n)
Yeo
2
Você pode obter o primeiro min / max, mas obter o k / min / max voltaria à complexidade normal do BST.
Caos
3

Uma árvore de pesquisa binária usa a definição: que para cada nó, o nó à esquerda dele tem um valor menor (chave) e o nó à direita dele tem um valor maior (chave).

Onde, como heap, ser uma implementação de uma árvore binária usa a seguinte definição:

Se A e B são nós, em que B é o nó filho de A, o valor (chave) de A deve ser maior ou igual ao valor (chave) de B. Ou seja, chave (A) ≥ chave (B )

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

Fiz a mesma pergunta hoje para o meu exame e acertei. sorriso ... :)

Yevgraf Andreyevich Zhivago
fonte
"pilha, sendo uma implementação de árvore binária" - apenas apontando que uma pilha é uma espécie de árvore binária, e não um tipo de BST
Saad
3

Outro uso do BST sobre Heap; por causa de uma diferença importante:

  • encontrar sucessor e predecessor em um BST levará tempo O (h). (O (logn) em BST balanceado)
  • enquanto em Heap, levaria O (n) tempo para encontrar sucessor ou predecessor de algum elemento.

Uso do BST sobre uma pilha : Agora, vamos dizer que usamos uma estrutura de dados para armazenar o tempo de aterrissagem de voos. Não podemos agendar um voo para pousar se a diferença nos tempos de pouso for menor que 'd'. E suponha que muitos voos foram programados para pousar em uma estrutura de dados (BST ou Heap).

Agora, queremos agendar outro voo que aterrissará em t . Portanto, precisamos calcular a diferença de t com seu sucessor e predecessor (deve ser> d). Assim, precisaremos de um BST para isso, o que faz rápido, ou seja, em O (logn) se equilibrado.

Editado:

A classificação do BST leva O (n) tempo para imprimir os elementos na ordem classificada (travessia de pedidos), enquanto o Heap pode fazê-lo no tempo O (n logn). O heap extrai o elemento min e re-heapifica a matriz, o que faz a classificação no tempo O (n logn).

CODError
fonte
1
Sim. É de sequência não classificada para ordenada. O (n) tempo para a travessia inorder de um BST, que fornece a sequência classificada. Enquanto estiver no Heaps, você extrai o elemento min e re-heapify no tempo O (log n). SO, será necessário O (n logn) para extrair n elementos. E isso deixará você com uma sequência classificada.
precisa
from unsorted to sorted sequence. O(n) time for inorder traversal of a BST, which gives sorted sequence.Bem, da sequência não classificada ao BST, não conheço um método baseado na comparação de chaves com menos de O (n logn), que domina o BST para a parte da sequência. (Considerando que há O (n) construção de heap.). Eu consideraria justo (se inútil) afirmar que os montes estão próximos da falta de classificação e os BSTs classificados.
Greybeard
O que estou tentando explicar aqui é que, se você tiver um BST e também um monte de n elementos =>, todos os elementos poderão ser impressos em ordem classificada nas estruturas de dados e o BST poderá fazê-lo em O (n) tempo ), enquanto o Heap levaria tempo O (n logn). Não entendo o que você está tentando dizer aqui. How do you say O BST fornecerá a sequência classificada em O (n logn).
precisa
Eu acho que você também está considerando o tempo necessário para construir um BST e um Heap. Mas suponho que você já o tenha, que o tenha construído ao longo do tempo e agora deseja obter o resultado classificado. Eu não estou entendendo o seu ponto?
precisa saber é o seguinte
1
Editado ... Espero que esteja satisfeito agora; p e dê um +1 se estiver correto.
CODError
1

Inserir todos os n elementos de uma matriz no BST leva O (n logn). n elemnts em uma matriz podem ser inseridos em um heap em O (n) time. O que dá à pilha uma vantagem definitiva

AMR
fonte
0

O heap apenas garante que os elementos em níveis mais altos sejam maiores (para max-heap) ou menores (para min-heap) do que os elementos em níveis mais baixos

Adoro a resposta acima e coloco meu comentário apenas mais específico para minha necessidade e uso. Eu tive que obter a lista de n localizações, encontrar a distância de cada local até o ponto específico, digamos (0,0) e depois retornar os locais am com menor distância. Eu usei a fila de prioridade, que é a pilha. Para encontrar distâncias e colocar heap, levei n (log (n)) n-local log (n) cada inserção. Então, para obter m com distâncias mais curtas, foram necessárias m (log (n)) localizações m log (n) exclusões de empilhamento.

Se eu tivesse que fazer isso com o BST, seria necessário n (n) pior inserção do caso (digamos que o primeiro valor seja muito menor e todo o outro venha sequencialmente mais e mais e mais, e a árvore se estenda para o filho direito ou filho esquerdo) no caso de cada vez menor, o minuto levaria tempo O (1), mas novamente eu tinha que me equilibrar.Então, da minha situação e de todas as respostas acima, o que eu recebi é quando você está atrás apenas dos valores com base na prioridade mínima ou máxima para pilha.

Sahib Khan
fonte