Qual ' sa diferença entre uma árvore de pesquisa binária e um heap binário?

O heap apenas garante que os elementos em níveis superiores sejam maiores (para heap máximo) ou menores (para heap mínimo) do que elementos em níveis inferiores, enquanto o BST garante a ordem (da “esquerda” para a “direita”) . Se você quiser elementos classificados, vá com BST. por Dante não é um geek

Heap é melhor em findMin / findMax (O ( 1)), enquanto BST é bom em todas as descobertas (O (logN)). Insert é O (logN) para ambas as estruturas. Se você só se preocupa com findMin / findMax (por exemplo, relacionado à prioridade), vá com heap. tudo classificado, vá com BST.

por xysun

Comentários

• Eu acho que BST é melhor em findMin & findMax stackoverflow .com / a / 27074221/764592
• Acho que é apenas um comunicado em equívoco. Uma árvore binária pode ser facilmente modificada para encontrar o mínimo e o máximo conforme apontado por Yeo. Esta é na verdade uma restrição do heap: o único achado eficiente é mínimo ou máximo. A verdadeira vantagem do heap é O (1) inserção média , conforme explico: stackoverflow.com/a/29548834/895245
• De acordo com este vídeo , você pode ter valores maiores em um nível inferior, desde que o maior não seja descendente do inferior.
• O heap é classificado da raiz para a folha e o BST é classificado da esquerda para a direita.
• e se eu quiser encontrar a mediana em tempo constante e remover a mediana em tempo logarítmico? qual estrutura de dados devo escolher? a implementação do MinHeap funcionará? sugira.

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 seus piores tempos, exceto para inserir.

• *: em toda parte nesta resposta, BST == BST balanceado, uma vez que desequilibrado suga assintoticamente
• **: usando uma modificação trivial explicada nesta resposta
• ***: log(n) para o heap da árvore do ponteiro, n para heap de array dinâmico

Vantagens do heap binário sobre BST

• O tempo médio de inserção em um heap binário é O(1), pois BST é O(log(n)). Este é o recurso matador dos heaps.

  Existem também outros heaps que alcançam O(1) amortizado (mais forte) como o Fibonacci Heap , e ainda pior caso, como o Fila Brodal , embora possam não ser práticos devido ao desempenho não assintótico: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• heaps binários podem ser implementados com eficiência em cima de matrizes dinâmicas ou árvores baseadas em ponteiros, apenas BST árvores baseadas em ponteiros. Portanto, para o heap, podemos escolher a implementação de array mais eficiente em termos de espaço, se pudermos permitir latências de redimensionamento ocasionais.

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

Vantagem do BST sobre o heap binário

• a pesquisa de elementos arbitrários é O(log(n)). Este é o recurso matador dos BSTs.

  Para heap, é O(n) em geral, exceto para o maior elemento que é O(1).

Vantagem “falsa” do heap sobre o BST

• heap é O(1) para encontrar o máximo, BST O(log(n)).

  Isso é um equívoco comum, porque é trivial modificar um BST para rastrear o maior elemento e atualizá-lo sempre que esse elemento puder ser alterado: na inserção de um swap maior, na remoção, encontre o segundo maior. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (mencionado por Yeo ).

  Na verdade, esta é uma limitação dos heaps comparados aos BSTs: a única busca eficiente é aquela para o maior elemento.

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

Fontes:

• Artigo: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Slides WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argumento intuitivo:

• os níveis inferiores da árvore têm exponencialmente mais elementos do que os níveis superiores, portanto, é quase certo que os novos elementos irão para o fundo
• inserção de heap começa de baixo , o BST deve começar de cima

Em um heap binário, aumentar o valor em um determinado índice também é O(1) pelo mesmo motivo. Mas se você quiser fazer isso, é provável que queira manter um índice extra atualizado nas operações de heap https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu por exemplo para Dijkstra. Possível sem custo adicional de tempo.

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

Eu comparei o C ++ std::set ( Red-black tree BST ) e std::priority_queue ( heap de matriz dinâmica ) insira para ver se eu estava certo sobre os tempos de inserção, e isto é o que obtive:

• código de referência
• script de plotagem
• dados do gráfico
• 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 claro:

• heap insert t ime é basicamente constante.

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

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

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

• Análise detalhada BST vs hashmap em: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

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

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

Interpretação:

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

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

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

  Com esse detalhe maior, no entanto, podemos ver também podemos ver algumas linhas distintas, mas não tenho certeza do que elas representam: eu esperaria que o resultado final ser mais fino, uma vez que inserimos a parte superior inferior?

Comparado com esta Configuração Buildroot em um aarch64 CPU HPI .

O BST não pode ser implementado de forma eficiente em uma matriz

Pilha as operações só precisam subir ou descer um único galho de árvore, então O(log(n)) trocas de pior caso, O(1) média.

Manter um BST equilibrado requer rotações de árvore, o que pode mudar o elemento superior por outro, e exigiria a movimentação de todo o array (O(n)).

Heaps podem ser implementados com eficiência em uma matriz

Índices pais e filhos 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 tem que ser de cima para baixo. Mas isso sempre pode ser feito “percolando” um único ramo do heap como explicado aqui . Isso leva a um pior caso O (log (n)), uma vez que o heap está sempre bem balanceado.

Se você inserir um único nó para cada um que remover, perderá a vantagem do assintótico O (1) inserção média que heaps fornecem, já que a exclusão dominaria, e você também pode usar um BST. O Dijkstra, entretanto, atualiza os nós várias vezes a cada remoção, então estamos bem.

Pilhas de array dinâmicas vs pilhas de árvores de ponteiros

Pilhas podem ser implementadas com eficiência no topo dos montes de ponteiro: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

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

• a implementação da árvore deve armazenar três ponteiros para cada elemento: pai, criança esquerda e criança direita. Portanto, o uso de memória é sempre 4n (3 ponteiros de árvore + 1 ponteiro struct).

  BSTs de árvore também precisa de mais informações de equilíbrio, por exemplo black-red-ness.

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

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

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

Filosofia

• BSTs mantêm uma propriedade global entre um pai e todos os descendentes (esquerdo menor, direito maior).

  O nó superior de um BST é o elemento do meio , que requer conhecimento global para ser mantido (saber quantos elementos menores e maiores existem).

  Esta propriedade global é mais cara de manter (log n inserir), mas fornece pesquisas mais poderosas (log n pesquisa) .

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

  A nota principal de um heap é o grande elemento, que requer apenas conhecimento local para se manter (conhecer seus pais).

Comparando BST vs Heap vs Hashmap:

• BST: pode ser um razoável:

  • conjunto não ordenado (uma estrutura que determina se um elemento foi inserido anteriormente ou não). Mas o hashmap tende a ser melhor devido à inserção amortizada O (1).
  • máquina de classificação. Mas heap geralmente é melhor nisso, e é por isso que heapsort é muito mais conhecido do que tree sort

• heap: é apenas uma máquina de classificação. Não pode ser um conjunto não ordenado eficiente, porque você só pode verificar rapidamente o menor / maior elemento.

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

Lista duplamente vinculada

Uma lista duplamente ligada pode ser vista como um subconjunto do heap onde 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.
    • heap binário: o item inserido pode terminar em qualquer posição. Menos restritivo do que a lista vinculada.
  • tempo:
    • lista duplamente vinculada: O(1) pior caso, já que temos ponteiros para os itens, e a atualização é realmente simples
    • heap binário: O(1) média, portanto pior do que a lista vinculada. tendo 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, as novas entradas sempre irão para o início da lista. Portanto, podemos até mesmo esquecer o carimbo de data / hora exato e apenas manter a posição na lista como a prioridade.

Isso pode ser usado para implementar um cache LRU . Assim como para aplicativos de heap como Dijkstra , você desejará manter um hashmap adicional da chave para o nó correspondente da lista, para encontrar qual nó atualizar rapidamente .

Comparação de diferentes BST balanceado

Embora a inserção e localização assintótica vezes para todas as estruturas de dados que são comumente classificadas como “BSTs balanceados” que eu vi até agora é o mesmo, BBSTs diferentes têm compensações diferentes. Eu não estudei completamente isso ainda, mas seria bom resumir essas compensações aqui:

• Árvore vermelho-preto . Parece ser o BBST mais comumente usado em 2019, por ex. é o usado pela implementação GCC 8.3.0 C ++
• árvore AVL . Parece ser um pouco mais equilibrado que o BST, então poderia ser melhor para a latência de localização, ao custo de descobertas um pouco mais caras.O Wiki resume: “As árvores AVL são frequentemente comparadas às árvores vermelhas e pretas porque ambas suportam o mesmo conjunto de operações e levam [o mesmo] tempo para as operações básicas. Para aplicativos de pesquisa intensiva, as árvores AVL são mais rápidas do que as árvores vermelhas e pretas porque elas são mais estritamente equilibradas. Semelhante às árvores vermelho-pretas, as árvores AVL são equilibradas em altura. Ambas, em geral, não têm equilíbrio de peso nem equilíbrio de mu para qualquer mu < 1 / 2; isto é, nós irmãos podem ter um número muito diferente de descendentes. “
• WAVL . O artigo original menciona as vantagens dessa versão em termos de limites nas operações de rebalanceamento e rotação.

Veja também

Pergunta semelhante no CS: O que ' é a diferença entre uma árvore de pesquisa binária e um heap binário?

Comentários

• Ótima resposta . As aplicações comuns de heap são mediana, k min, top k elementos. Para essas operações mais comuns, remova min e insira (geralmente temos um pequeno heap com poucas operações de inserção puras). Parece que na prática, para esses algoritmos, ele não supera o BST.
• Resposta excepcional !!! Usando deque como estrutura de heap subjacente, você pode reduzir drasticamente os tempos de redimensionamento, embora ainda seja O (n) o pior caso, já que precisa realocar (menor) array de ponteiros para blocos.

Ambas as árvores de pesquisa binárias e heaps binários são estruturas de dados baseadas em árvore.

Heaps exigem que os nós tenham prioridade sobre seus filhos. Em um heap máximo, os filhos de cada nó devem ser menores do que ele mesmo. Isso é o oposto de um heap mínimo:

Árvores binárias de pesquisa (BST) seguem uma ordem específica (pré-ordem, ordem, pós-ordem) entre os nós irmãos. A árvore deve ser classificado, ao contrário de heaps:

BST tem média de $ O (\ log n) $ para inserção, exclusão e pesquisa.
Heaps binários têm $ O (1) $ média para findMin / findMax e $ O (\ log n) $ para inserção e exclusão.

Comentários

• @FrankW Extração é $ O (\ log n) $, não?

Além das respostas anteriores, o heap deve ter a propriedade de estrutura do heap ; a árvore deve estar cheia, e a camada mais inferior, que nem sempre pode estar cheia, deve ser preenchida da esquerda para a direita, sem lacunas.