Qual é a vantagem de pilhas sobre matrizes classificadas?

7

Sou bastante novo em heaps e estou tentando entender por que min e max são representados como árvores quando uma matriz classificada parece fornecer propriedades mín / máx por padrão.

E um acompanhamento: qual é a vantagem de lidar com a complexidade de inserir em um heap, dado um algoritmo como a ordenação rápida manipula a classificação muito bem?

Contexto: Estou trabalhando no CLRS / MIT 6.006 em python e só vi representações inteiras de valores de folhas. Isso é mais aplicável em um idioma como C, em que cada folha contém uma estrutura que não pode ser facilmente classificada?

Nick Olinger
fonte
2
Observe que os montes geralmente são modelados como árvores, mas implementados como matrizes, se não da maneira que você propõe.
Raphael

Respostas:

14

find-min (resp. ), (resp. ) e são as três operações mais importantes de um min-heap (resp. max-heap) e geralmente possuem complexidade de , e respectivamente, se você implementar um min / max-heap por uma árvore binária.find-maxdelete-mindelete-maxinsertO(1)O(logn)O(logn)


Agora, suponha que você implemente um min-heap por uma matriz classificada (não decrescente) (o caso do max-heap é semelhante). e têm complexidade de se não for necessário em seu aplicativo, pois você pode mantenha um ponteiro que sempre aponte para o elemento mínimo em sua matriz. Quando o elemento mínimo é removido, você só precisa mover um passo para o próximo elemento na matriz.find-mindelete-minO(1)insertpp

Lidar com a inserção em uma matriz classificada não é trivial. Dado um novo elemento , podemos usar a pesquisa binária para localizar sua posição na matriz para inseri-lo. Mas o ponto é que, se você deseja inseri-lo lá, é necessário mover muitos elementos antigos (pode ser ) para criar uma vaga para o novo elemento residir. Isso é bastante ineficiente para a maioria dos aplicativos. Você também pode optar por reordenar a matriz após a inserção de um elemento ; no entanto , isso requer tempo .eO(n)O(nlogn)


O último ponto, como você implementa uma estrutura de dados realmente depende do seu aplicativo. Nenhuma implementação única é melhor para todos os casos. Analise seu aplicativo, descubra as operações mais frequentes e decida a implementação apropriada.

PSPACEhard
fonte
11
E a adição de um novo elemento não pode ser feita mais rapidamente que O (n) em uma matriz contígua, pois existem até n elementos que estão no lugar errado e devem ser movidos para um local diferente, não importa o que você faça.
gnasher729
Eu vejo. @ NP-hard Portanto, a principal vantagem de representar um monte de uma matriz classificada é o tempo de acesso a valores mínimo / máximo, mas a desvantagem é a inserção causada por "abrir espaço". Por outro lado, um heap representado como uma matriz não classificada tem a vantagem da inserção, pois só precisa trocar elementos até que as propriedades do heap sejam satisfeitas novamente, mas apresenta uma desvantagem de find-min/ find-maxno O (log n)?
27616 Nick Olinger
11
@LindyHop Sim. É uma troca. Mas requer apenas tempo; é que requer . find-minO(1)delete-minO(logn)
usar o seguinte comando
5

Para responder às suas perguntas, você deve definir quais ações diferentes serão executadas e com que frequência e avaliar a complexidade do tempo de cada ação.

Qual método tem um desempenho melhor geral dependerá das complexidades individuais e da frequência com que cada ação é executada.

A classificação de uma matriz tem uma complexidade de tempo muito alta; operações de pilha são tão baratas que são realmente usadas para uma implementação de classificação decente. Usar uma pilha para encontrar o menor elemento é definitivamente muito mais rápido do que classificar uma matriz. Dois montões para o elemento menor e maior ainda são muito mais rápidos (mas essa situação é bastante rara; por exemplo, em uma corrida de cavalos, todo mundo quer conhecer o vencedor, mas ninguém se importa com quem vem por último).

Onde um heap supera completamente as matrizes de classificação, é uma situação em que um pequeno número de itens é removido ou adicionado e, após cada alteração, você deseja saber novamente qual é o menor elemento.

gnasher729
fonte
Isso ajuda muito. Parece que uma implementação que exige muita pesquisa / inserções mínimas seria melhor implementada como um heap de matriz classificada; no entanto, um cenário com muitas inserções seria mais adequado para uma árvore heap / binária de matriz não classificada.
22616 Nick Olinger #