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

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?

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:

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

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:

• 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.

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

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.

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.

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.

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 ... :)

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).

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

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.