Qual é a vantagem de pilhas sobre matrizes classificadas?

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?

$\small \texttt{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.$\small \texttt{find-max}$$\small \texttt{delete-min}$$\small \texttt{delete-max}$$\small \texttt{insert}$$\small \mathcal{O}(1)$$\small \mathcal{O}(\log n)$$\small \mathcal{O}(\log n)$

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.$\small \texttt{find-min}$$\small \texttt{delete-min}$$\small \mathcal{O}(1)$$\small \texttt{insert}$$\small p$$\small p$

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 .$\small e$$\small \mathcal{O}(n)$$\small \mathcal{O}(n\log n)$

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.

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.