Estruturas de Dados: Heap

O Heap é uma estrutura de dados linear que organiza elementos em ordem de prioridade, com o maior elemento sempre no início. Representado como uma árvore binária completa, um Heap garante que cada nó pai tenha prioridade maior que seus filhos. Operações como seleção, inserção e remoção têm complexidade de O(log n), pois envolvem subir ou descer a árvore para manter a ordem. A alteração de prioridade também tem complexidade de O(log n). O algoritmo "subir" move elementos para cima na árvore se sua prioridade for maior que a dos pais. O algoritmo "descer" move elementos para baixo se sua prioridade for menor que a dos filhos. A inserção envolve adicionar um novo elemento ao final e subi-lo na árvore para manter a ordem. A remoção do elemento de maior prioridade envolve substituí-lo pelo último elemento e descer esse elemento para manter a ordem. Um Heap pode ser construído ordenando uma lista (O(n log n)) ou descendo os nós internos da árvore a partir da metade da lista (O(n)).