Heap
Árvore binária
Propriedade da forma
Todos níveis cheios
Exceto possivelmente o último
Apenas folhas mais à direita
Dominância parental
Chave em um nó é maior ou igual chave dos filhos
Heapify
Entrada array H[1...n]
Para i=n/2 diminuindo até 1 faça
k=i; v=H[k]; heap=falso
Enquanto !heap e 2*k<=n faça
j=2k
Se j<n
Se H[j]<H[j+1]
j=j+1
Se v>=H[j]
heap=verdadeiro
Caso contrário
H[k]=H[j]; k=j
H[k] = v
Saída heap H[1...n]
DeletarRaiz
Entrada heap H[1...n]
v=H[n]
H[n]=H[1]; H[1]=v
Saída Heapify(H[1...n-1])
Heapsort
Entrada array H[1...n]
Heapify(H[1...n])
Para i=n diminuindo até 2 faça
DeletarRaiz(H[1...i])
Saída array H[1...n]