Quais são as classificações de heaps no contexto de estruturas de dados?

No contexto das estruturas de dados, por "montículo" (Heap) entende-se geralmente um montículo binário (Binary Heap), que possui as seguintes classificações:

1. Por tipo de ordenação:

   • Montículo mínimo (Min-Heap): O valor de cada nó é menor ou igual aos valores dos seus nós filhos. A raiz é o elemento mínimo.
   • Montículo máximo (Max-Heap): O valor de cada nó é maior ou igual aos valores dos seus nós filhos. A raiz é o elemento máximo.

2. Por completude da árvore:

   • Montículo binário completo (Complete Binary Heap): Todos os níveis, exceto talvez o último, estão completamente preenchidos, e os nós no último nível estão o mais à esquerda possível. Essa propriedade é importante porque permite armazenar eficientemente o montículo em um array.

   // Exemplo de estrutura para um nó do montículo (para demonstrar o conceito)
   public class HeapNode<T>
   {
       public T Value { get; set; }
       // As referências aos nós filhos nem sempre são explícitas na representação em array
       public HeapNode<T> Left { get; set; }
       public HeapNode<T> Right { get; set; }
   }
   

Embora existam outros tipos de montículos, como o montículo de Fibonacci (para algoritmos avançados) ou o montículo binomial, na maioria dos casos, "montículo" refere-se especificamente a um montículo binário completo de mínimo ou máximo devido ao seu amplo uso em algoritmos de ordenação (por exemplo, Heapsort) e filas de prioridade.