Heaps vs. Stacks: O que os diferencia?
Como programador, você provavelmente já se deparou com os termos "heap" e "stack". É uma prática comum para iniciantes usar esses dois termos de forma intercambiável e incorreta.
Embora os alunos de um curso de Estruturas de Dados e programadores experientes possam distinguir facilmente entre essas duas estruturas de dados, elas podem parecer iguais para os outros.
Os programadores precisam diferenciar entre os dois e usá-los apropriadamente em situações práticas de programação. Os entrevistadores costumam apresentar um cenário aos candidatos e, em seguida, solicitar a estrutura de dados mais adequada.
Continue lendo enquanto damos uma olhada detalhada em heaps, pilhas, suas diferenças e aplicações relevantes.
O que é um heap?
Um heap para programadores é normalmente uma estrutura de dados em árvore especial, freqüentemente chamada de "fila de prioridade". Heaps que são uma estrutura de árvore binária completamente balanceada (lembre-se de que todos os níveis de uma árvore binária completa são preenchidos, exceto o último nível) e seguem uma propriedade de heap são chamados de Heaps Binários.
A propriedade heap estrutura a árvore de uma maneira que coloca o valor máximo ou mínimo na raiz.
Em um heap máximo, o valor dos nós pais é maior do que os nós filhos e a raiz da árvore contém o valor máximo. Como alternativa, um Min Heap é estruturado para ter o valor mínimo como raiz e cada nó filho tem um valor maior do que seu pai. A propriedade heap deve ser recursivamente verdadeira para cada nó na árvore binária.
Heaps são geralmente implementados por meio de matrizes lineares, com o primeiro elemento da matriz ( Arr [0] ) representando a raiz. Para um nó i específico, você pode recuperar os nós filhos em Arr [(2 * i) + 1] e Arr [(2 * i) + 2] , da mesma forma o nó pai está localizado em Arr [(i-1) / 2] índice. A maioria das linguagens, como Java e C ++, contém bibliotecas que fornecem aos usuários heaps mínimo e máximo prontos para uso.
O que é uma pilha?
As pilhas são uma das primeiras estruturas de dados ensinadas aos alunos e não devem ser esquecidas. Uma pilha é uma estrutura de dados que se comporta como qualquer pilha da vida real (cartões, pratos, etc.). As pilhas permitem operações apenas em uma extremidade e, como resultado, têm uma característica LIFO (Last-In-First-Out). Em contraste, as filas têm uma característica FIFO (First-In-First-Out) e permitem operações em ambas as extremidades.
As operações típicas de pilha consistem em push (inserir dados no topo da pilha) e pop (remover o elemento de dados no topo). Você pode implementar pilhas por meio de ponteiros, matrizes ou até mesmo listas vinculadas, dependendo de seus requisitos. C ++, C # e Java contêm bibliotecas que já implementaram uma pilha, portanto, você pode usá-las sempre que precisar.
Pilhas vs. Pilhas
Se você leu até aqui, tem uma boa ideia das diferenças entre uma pilha e um heap. As pilhas são lineares e têm uma característica LIFO, enquanto as pilhas têm uma estrutura em árvore e seguem a propriedade de pilha. Ambos têm aplicações diferentes que discutiremos na próxima seção.
Em termos de uma análise de complexidade de tempo assintótica, você pode construir um heap binário em O (n) e extrair o valor mínimo ou máximo em O (1). As inserções e exclusões podem ser realizadas em tempo O (log N). Em contraste, a inserção e exclusão levam O (1) tempo em uma pilha.
Aplicações Típicas
Pelas razões discutidas acima, os heaps são muito eficientes quando usados como uma fila prioritária. Algoritmos de gráfico como o Minimum Spanning Tree de Prim e o Shortest Path de Dijkstra normalmente utilizam heaps como a fila de prioridade. Outra aplicação importante de heaps é classificar uma matriz de forma eficiente em apenas tempo O (N logN); esta técnica de classificação é conhecida como "Classificação de pilha".
As pilhas também têm uma variedade de aplicativos críticos, como gerenciamento de memória e avaliação de expressão. Se você enfrentar um problema de codificação de retrocesso, pode ser uma boa ideia salvar o dia usando uma pilha.
Priorize Estruturas de Dados
Todo programador de sucesso dirá a você a importância de se tornar proficiente com estruturas de dados. É uma ótima ideia tentar entender e se sentir confortável usando diferentes estruturas de dados como e quando necessário, uma vez que é um conceito vital para todos os programadores.
