Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps - Coggle Diagram
Heaps
Conceito
Com exceção do último nível, todos os níveis da árvore binária devem estar cheios
O último nível é preenchido a partir da esquerda até certo ponto
Árvore Binária
Representando com uma array
Raíz da árvore no index 1
Começa no index 1
Seja um nó no index I
seu pai está em i/2
filho direito em 2i+1
seu filho esquerdo está em 2i
Tipos
Max-heap
Valor de um nó <= valor do pai deste nó
Heapsort
Min-heap
Valor de um nó >= valor do pai deste nó
Priority Queue
Heapsort
Usa max-heap
Etapas
Começe a iterar pela posição do último nó interno da árvore (n/2) até 1
Para cada index i da array
heap = false
Flag que indica se a posição correta de V foi encontrada
k = i
v = heapArr[i]
Guarda o valor incial do nó na posição i
Enquanto o nó k tiver pelo menos um filho à esquerda (2*k <= n) e a posição correta de v ainda não tiver sido encontrada:
Se o filho à direita existir (j < n) e for maior que o filho à esquerda (heapArr[j] < heapArr[j + 1]), então j = j + 1 (escolha o maior dos filhos).
v >= heapArr[j], a condição da max-heap está satisfeita → defina heap = true
caso contrário:
Atualize k = j e repita (desça na árvore).
Suba heapArr[j] para heapArr[k].
Defina j = 2 * k: Assuma que o filho à esquerda é o maior.
Quando a posição correta for encontrada, coloque v em heapArr[k].