Heapsort - Heapsort

Heapsort

Uma execução de heapsort classificando uma matriz de valores permutados aleatoriamente. No primeiro estágio do algoritmo, os elementos do array são reordenados para satisfazer a propriedade heap . Antes que a classificação real ocorra, a estrutura da árvore do heap é mostrada brevemente para ilustração.
Aula	Algoritmo de classificação
Estrutura de dados	Variedade
Desempenho de pior caso	${\ displaystyle O (n \ log n)}$
Melhor caso de desempenho	${\ displaystyle O (n \ log n)}$(chaves distintas) ou (chaves iguais)${\ displaystyle O (n)}$
Desempenho médio	${\ displaystyle O (n \ log n)}$
Pior caso de complexidade de espaço	${\ displaystyle O (n)}$auxiliar total${\ displaystyle O (1)}$

Na ciência da computação , o heapsort é um algoritmo de classificação baseado em comparação . O Heapsort pode ser considerado uma classificação de seleção aprimorada : como a classificação de seleção, o heapsort divide sua entrada em uma região classificada e uma não classificada e encolhe iterativamente a região não classificada, extraindo o maior elemento dela e inserindo-o na região classificada. Ao contrário da classificação por seleção, o heapsort não perde tempo com uma varredura de tempo linear da região não classificada; em vez disso, a classificação de heap mantém a região não classificada em uma estrutura de dados de heap para localizar mais rapidamente o maior elemento em cada etapa.

Embora um pouco mais lento na prática na maioria das máquinas do que um quicksort bem implementado , ele tem a vantagem de um tempo de execução O ( n log n ) de pior caso mais favorável . Heapsort é um algoritmo local , mas não é um tipo estável .

O Heapsort foi inventado por JWJ Williams em 1964. Este foi também o nascimento do heap, já apresentado por Williams como uma estrutura de dados útil em seu próprio direito. No mesmo ano, RW Floyd publicou uma versão aprimorada que poderia classificar um array no local, continuando sua pesquisa anterior no algoritmo de classificação de árvore .

Visão geral

O algoritmo heapsort pode ser dividido em duas partes.

Na primeira etapa, um heap é criado a partir dos dados (consulte Heap binário § Construindo um heap ). O heap é freqüentemente colocado em uma matriz com o layout de uma árvore binária completa . A árvore binária completa mapeia a estrutura da árvore binária nos índices do array; cada índice de array representa um nó; o índice do pai do nó, do ramo filho esquerdo ou do ramo filho direito são expressões simples. Para uma matriz baseada em zero, o nó raiz é armazenado no índice 0; se ifor o índice do nó atual, então

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

Na segunda etapa, um array classificado é criado removendo repetidamente o maior elemento do heap (a raiz do heap) e inserindo-o no array. O heap é atualizado após cada remoção para manter a propriedade do heap. Depois que todos os objetos foram removidos do heap, o resultado é uma matriz classificada.

O Heapsort pode ser executado no local. O array pode ser dividido em duas partes, o array ordenado e o heap. O armazenamento de heaps como matrizes é diagramado aqui . O invariante do heap é preservado após cada extração, portanto, o único custo é o da extração.

Algoritmo

O algoritmo Heapsort envolve a preparação da lista, primeiro transformando-a em um heap máximo . O algoritmo então troca repetidamente o primeiro valor da lista pelo último valor, diminuindo o intervalo de valores considerados na operação de heap em um, e peneirando o novo primeiro valor em sua posição no heap. Isso se repete até que o intervalo de valores considerados tenha um valor de comprimento.

As etapas são:

1. Chame a função buildMaxHeap () na lista. Também conhecido como heapify (), cria um heap a partir de uma lista em operações O (n).
2. Troque o primeiro elemento da lista pelo elemento final. Diminua o intervalo considerado da lista em um.
3. Chame a função siftDown () na lista para filtrar o novo primeiro elemento para seu índice apropriado no heap.
4. Vá para a etapa (2), a menos que o intervalo considerado da lista seja um elemento.

A operação buildMaxHeap () é executada uma vez e tem desempenho O ( n ) . A função siftDown () é O (log n ) e é chamada n vezes. Portanto, o desempenho desse algoritmo é O ( n + n log n ) = O ( n log n ) .

Pseudo-código

A seguir está uma maneira simples de implementar o algoritmo em pseudocódigo . Os arrays são baseados em zero e swapsão usados ​​para trocar dois elementos do array. Movimento 'para baixo' significa da raiz em direção às folhas, ou de índices mais baixos para mais altos. Observe que durante a classificação, o maior elemento está na raiz do heap em a[0], enquanto no final da classificação, o maior elemento está em a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

A rotina de classificação usa duas sub-rotinas heapifye siftDown. A primeira é a rotina comum de construção de heap in-loco, enquanto a última é uma sub-rotina comum para implementação heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

O heapifyprocedimento pode ser pensado como a construção de um heap de baixo para cima, peneirando sucessivamente para baixo para estabelecer a propriedade do heap . Uma versão alternativa (mostrada abaixo) que constrói o heap de cima para baixo e peneirar para cima pode ser mais simples de entender. Esta siftUpversão pode ser visualizada como começando com um heap vazio e inserindo elementos sucessivamente, enquanto a siftDownversão fornecida acima trata toda a matriz de entrada como um heap cheio, mas "quebrado" e "repara" a partir do último sub-heap não trivial ( ou seja, o último nó pai).

Diferença na complexidade de tempo entre a versão "siftDown" e a versão "siftUp".

Além disso, a siftDownversão do heapify tem complexidade de tempo O ( n ) , enquanto a siftUpversão fornecida abaixo tem complexidade de tempo O ( n log n ) devido à sua equivalência com a inserção de cada elemento, um de cada vez, em um heap vazio. Isso pode parecer contra-intuitivo, pois, à primeira vista, é aparente que o primeiro faz apenas metade das chamadas para sua função de peneiração no tempo logarítmico do que o último; isto é, eles parecem diferir apenas por um fator constante, que nunca afeta a análise assintótica.

Para entender a intuição por trás dessa diferença de complexidade, observe que o número de trocas que podem ocorrer durante qualquer chamada de siftUp aumenta com a profundidade do nó em que a chamada é feita. O ponto crucial é que há muitos (exponencialmente muitos) mais nós "profundos" do que nós "rasos" em um heap, de modo que o siftUp pode ter seu tempo de execução logarítmico completo no número aproximadamente linear de chamadas feitas nos nós em ou perto do "fundo" da pilha. Por outro lado, o número de trocas que podem ocorrer durante qualquer chamada siftDown diminui à medida que aumenta a profundidade do nó no qual a chamada é feita. Assim, quando o siftDown heapifycomeça e está chamando siftDownnas camadas de nós inferiores e mais numerosas, cada chamada de peneiramento incorrerá, no máximo, em um número de trocas igual à "altura" (da parte inferior da pilha) do nó em que a chamada de peneiração é feita. Em outras palavras, cerca de metade das chamadas para siftDown terão no máximo apenas uma troca, então cerca de um quarto das chamadas terá no máximo duas trocas, etc.

O próprio algoritmo heapsort tem complexidade de tempo O ( n log n ) usando qualquer uma das versões do heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Observe que, ao contrário da siftDownabordagem em que, após cada troca, você precisa chamar apenas a siftDownsub-rotina para consertar o heap quebrado; a siftUpsub - rotina sozinha não pode consertar o heap quebrado. O heap precisa ser construído todas as vezes após uma troca chamando o heapifyprocedimento, uma vez que "siftUp" assume que o elemento que está sendo trocado termina em seu lugar final, ao contrário de "siftDown" permite ajustes contínuos de itens inferiores no heap até que invariante está satisfeito. O pseudocódigo ajustado para usar a siftUpabordagem é fornecido abaixo.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Variações

Construção de heap de Floyd

A variação mais importante do algoritmo básico, que está incluído em todas as implementações práticas, é um algoritmo de construção de heap do Floyd que roda em tempo O ( n ) e usa siftdown em vez de siftup , evitando a necessidade de implementar o siftup.

Em vez de começar com uma pilha trivial e adicionar folhas repetidamente, o algoritmo do Floyd começa com as folhas, observando que elas são pilhas triviais, mas válidas por si mesmas, e então adiciona os pais. Começando com o elemento n / 2 e trabalhando para trás, cada nó interno torna-se a raiz de um heap válido por meio da peneira. A última etapa é filtrar o primeiro elemento, após o qual toda a matriz obedece à propriedade heap.

O número de pior caso de comparações durante a fase de construção de heap do Floyd do Heapsort é conhecido por ser igual a 2 n - 2 s ₂ ( n ) - e ₂ ( n ) , onde s ₂ ( n ) é o número de 1 bits na representação binária de n e e ₂ ( n ) é o número de fuga 0 bits.

A implementação padrão do algoritmo de construção de heap do Floyd causa um grande número de perdas de cache, uma vez que o tamanho dos dados excede o do cache da CPU . Um desempenho muito melhor em grandes conjuntos de dados pode ser obtido mesclando em profundidade-primeira ordem, combinando subhaps o mais rápido possível, em vez de combinar todos os subhaps em um nível antes de prosseguir para o nível acima.

Heapsort de baixo para cima

O heapsort ascendente é uma variante que reduz o número de comparações exigidas por um fator significativo. Enquanto o heapsort comum requer 2 n log ₂ n + O ( n ) comparações de pior caso e em média, a variante ascendente requer n log ₂ n + O (1) comparações em média e 1,5 n log ₂ n + O ( n ) no pior caso.

Se as comparações forem baratas (por exemplo, chaves inteiras), a diferença não é importante, pois o heapsort top-down compara valores que já foram carregados da memória. Se, no entanto, as comparações exigem uma chamada de função ou outra lógica complexa, o heapsort ascendente é vantajoso.

Isso é feito melhorando o siftDownprocedimento. A mudança melhora um pouco a fase de construção de heap de tempo linear, mas é mais significativa na segunda fase. Como o heapsort comum, cada iteração da segunda fase extrai o topo do heap, a [0] , e preenche a lacuna que deixa com um [ fim ] e , em seguida, peneirar este último elemento no heap. Mas esse elemento vem do nível mais baixo do heap, o que significa que é um dos menores elementos do heap, então a peneira provavelmente levará muitos passos para movê-lo de volta para baixo. No heapsort comum, cada etapa do peneiramento requer duas comparações, para encontrar o mínimo de três elementos: o novo nó e seus dois filhos.

Em vez disso, o heapsort ascendente encontra o caminho dos filhos maiores até o nível folha da árvore (como se estivesse inserindo −∞) usando apenas uma comparação por nível. Dito de outra forma, ele encontra uma folha que tem a propriedade de que ela e todos os seus ancestrais são maiores ou iguais aos seus irmãos. (Na ausência de chaves iguais, esta folha é única.) Então, a partir desta folha, ela pesquisa para cima (usando uma comparação por nível) para a posição correta nesse caminho para inserir um [ fim ] . Este é o mesmo local que os achados de heapsort comuns e requer o mesmo número de trocas para realizar a inserção, mas menos comparações são necessárias para encontrar esse local.

Como vai até o fundo e depois volta para cima, é chamado de heapsort com salto por alguns autores.

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

O valor de retorno de leafSearché usado na siftDownrotina modificada :

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

O heapsort bottom-up foi anunciado como quicksort vitorioso (com seleção de pivô em mediana de três) em matrizes de tamanho ≥16000.

Uma reavaliação de 2008 desse algoritmo mostrou que ele não era mais rápido do que o heapsort comum para chaves inteiras, presumivelmente porque a previsão de ramificação moderna anula o custo das comparações previsíveis que o heapsort bottom-up consegue evitar.

Um refinamento adicional faz uma pesquisa binária no caminho para a folha selecionada e classifica no pior caso de ( n +1) (log ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1,82) + O (log ₂ n ) comparações, aproximando -se do limite inferior teórico da informação de n log ₂ n - 1,4427 n comparações.

Uma variante que usa dois bits extras por nó interno ( total de n -1 bits para um heap de n- elementos) para armazenar informações sobre qual filho é maior (dois bits são necessários para armazenar três casos: esquerdo, direito e desconhecido) usa menos do que n log ₂ n + 1,1 n compara.

Outras variações

• O heapsort ternário usa um heap ternário em vez de um heap binário; ou seja, cada elemento no heap tem três filhos. É mais complicado de programar, mas executa um número constante de vezes menos operações de troca e comparação. Isso ocorre porque cada etapa de depuração em um heap ternário requer três comparações e uma troca, enquanto em um heap binário são necessárias duas comparações e uma troca. Dois níveis em um heap ternário cobrem 3 ² = 9 elementos, fazendo mais trabalho com o mesmo número de comparações que três níveis no heap binário, que cobre apenas 2 ³ = 8. Isso é principalmente de interesse acadêmico ou como um exercício de estudante , já que a complexidade adicional não compensa a pequena economia, e o heapsort ascendente supera ambos.
• O heapsort com otimização de memória melhora a localidade de referência do heapsort, aumentando ainda mais o número de filhos. Isso aumenta o número de comparações, mas como todos os filhos são armazenados consecutivamente na memória, reduz o número de linhas de cache acessadas durante a travessia de heap, uma melhoria de desempenho da rede.
• O heapsort fora do local melhora no heapsort ascendente eliminando o pior caso, garantindo n log ₂ n + O ( n ) comparações. Quando o máximo é obtido, em vez de preencher o espaço vazio com um valor de dados não classificado, preencha-o com um valor sentinela −∞ , que nunca "retorna". Acontece que isso pode ser usado como uma primitiva em um algoritmo "QuickHeapsort" no local (e não recursivo). Primeiro, você executa uma passagem de particionamento do tipo quicksort, mas invertendo a ordem dos dados particionados no array. Suponha ( sem perda de generalidade ) que a partição menor seja maior do que o pivô, que deve ficar no final da matriz, mas nossa etapa de particionamento reversa a coloca no início. Forme um heap com a partição menor e faça o heapsort fora do local, trocando os máximos extraídos pelos valores do final do array. Eles são menores do que o pivô, o que significa menos do que qualquer valor no heap, portanto, servem como valores de sentinela −∞ . Depois que o heapsort é concluído (e o pivô é movido para um pouco antes do final agora classificado do array), a ordem das partições foi invertida e a partição maior no início do array pode ser classificada da mesma maneira. (Como não há recursão não cauda , isso também elimina o uso da pilha O (log n ) do quicksort .)
• O algoritmo smoothsort é uma variação do heapsort desenvolvido por Edsger Dijkstra em 1981. Como o heapsort, o limite superior do smoothsort é O ( n log n ) . A vantagem do smoothsort é que ele se aproxima do tempo O ( n ) se a entrada já estiver classificada em algum grau , enquanto o heapsort tem a média de O ( n log n ), independentemente do estado inicial classificado. Devido à sua complexidade, o smoothsort raramente é usado.
• Levcopoulos e Petersson descrevem uma variação de heapsort baseada em um monte de árvores cartesianas . Primeiro, uma árvore cartesiana é construída a partir da entrada no tempo O ( n ) e sua raiz é colocada em um heap binário de 1 elemento. Em seguida, extraímos repetidamente o mínimo do heap binário, geramos o elemento raiz da árvore e adicionamos seus filhos esquerdo e direito (se houver), que são árvores cartesianas, ao heap binário. Como mostram, se a entrada já estiver quase classificada, as árvores cartesianas ficarão muito desequilibradas, com poucos nós tendo filhos à esquerda e à direita, resultando no heap binário permanecendo pequeno e permitindo que o algoritmo classifique mais rapidamente do que O ( n log n ) para entradas que já estão quase classificadas.
• Diversas variantes, como o heapsort fraco, requerem n log ₂ n + O (1) comparações no pior caso, perto do mínimo teórico, usando um bit extra de estado por nó. Embora esse bit extra faça com que os algoritmos não estejam realmente no lugar, se o espaço para ele puder ser encontrado dentro do elemento, esses algoritmos são simples e eficientes, mas ainda mais lentos do que heaps binários se as comparações de chave forem baratas o suficiente (por exemplo, chaves inteiras) que um fator constante não importa.
• O "último heapsort" de Katajainen não requer armazenamento extra, executa n log ₂ n + O (1) comparações e um número semelhante de movimentos de elementos. É, no entanto, ainda mais complexo e não justificado, a menos que as comparações sejam muito caras.

Comparação com outros tipos

O Heapsort compete principalmente com o quicksort , outro algoritmo de classificação baseado em comparação local muito eficiente de propósito geral.

As principais vantagens do Heapsort são seu código simples e não recursivo , requisito de armazenamento auxiliar mínimo e desempenho confiável: seus melhores e piores casos estão dentro de um pequeno fator constante um do outro e do limite inferior teórico em tipos de comparação . Embora não possa fazer melhor do que O ( n log n ) para entradas pré-classificadas, ele também não sofre do pior caso O ( n ² ) do quicksort . (O último pode ser evitado com uma implementação cuidadosa, mas isso torna o quicksort muito mais complexo e uma das soluções mais populares, o introsort , usa o heapsort para essa finalidade.)

Suas principais desvantagens são sua má localização de referência e sua natureza inerentemente serial; os acessos à árvore implícita são amplamente dispersos e principalmente aleatórios, e não há uma maneira direta de convertê-la em um algoritmo paralelo .

Isso o torna popular em sistemas embarcados , computação em tempo real e sistemas preocupados com entradas escolhidas maliciosamente, como o kernel Linux. Também é uma boa escolha para qualquer aplicativo que não espera ter gargalos na classificação.

Um quicksort bem implementado é geralmente 2–3 vezes mais rápido que o heapsort. Embora o quicksort exija menos comparações, esse é um fator menor. (Os resultados que reivindicam o dobro de comparações estão medindo a versão de cima para baixo; consulte § heapsort de baixo para cima .) A principal vantagem do quicksort é sua localidade de referência muito melhor: o particionamento é uma varredura linear com boa localidade espacial e a subdivisão recursiva tem boa localidade temporal. Com esforço adicional, o quicksort também pode ser implementado em código quase sem ramificações e várias CPUs podem ser usadas para classificar subpartições em paralelo. Assim, o quicksort é preferido quando o desempenho adicional justifica o esforço de implementação.

O outro algoritmo de classificação O ( n log n ) principal é a classificação por mesclagem , mas que raramente compete diretamente com o heapsort porque não está no lugar. O requisito de merge sort para Ω ( n ) espaço extra (aproximadamente metade do tamanho da entrada) é geralmente proibitivo, exceto nas situações em que merge sort tem uma vantagem clara:

• Quando uma classificação estável é necessária
• Ao aproveitar a entrada (parcialmente) pré-classificada
• Classificação de listas vinculadas (nesse caso, a classificação por mesclagem requer o mínimo de espaço extra)
• Classificação paralela; merge sort paraleliza ainda melhor do que quicksort e pode facilmente atingir um aumento de velocidade próximo ao linear
• Classificação externa ; merge sort tem excelente localidade de referência

Exemplo

Seja {6, 5, 3, 1, 8, 7, 2, 4} a lista que queremos classificar da menor para a maior. (OBSERVAÇÃO, para a etapa 'Construindo o Heap': nós maiores não ficam abaixo dos pais de nós menores. Eles são trocados com os pais e, em seguida, verificados recursivamente se outra troca é necessária, para manter números maiores acima de números menores na árvore binária do heap .)

Um exemplo no heapsort.

Notas

Referências

• Williams, JWJ (1964), "Algorithm 232 - Heapsort", Communications of the ACM , 7 (6): 347-348, doi : 10.1145 / 512274.512284
• Floyd, Robert W. (1964), "Algorithm 245 - Treesort 3", Communications of the ACM , 7 (12): 701, doi : 10.1145 / 355588.365103 , S2CID  52864987
• Carlsson, Svante (1987), "Average-case results on heapsort", BIT , 27 (1): 2-17, doi : 10.1007 / bf01937350 , S2CID  31450060
• Knuth, Donald (1997), "§5.2.3, Sorting by Selection", Sorting and Searching , The Art of Computer Programming , 3 (terceira ed.), Addison-Wesley, pp. 144-155, ISBN 978-0-201-89685-5
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 2001. ISBN  0-262-03293-7 . Capítulos 6 e 7, respectivamente: Heapsort e filas prioritárias
• Um PDF do artigo original de Dijkstra no Smoothsort
• Tutorial de Heaps and Heapsort por David Carlson, St. Vincent College

links externos

• Algoritmos de classificação animados: classificação de heap na máquina de retorno (arquivado em 6 de março de 2015) - demonstração gráfica
• Material didático sobre o Heapsort da Univ. Oldenburg - Com texto, animações e exercícios interativos
• Dicionário de Algoritmos e Estruturas de Dados do NIST: Heapsort
• Heapsort implementado em 12 idiomas
• Classificação revisitada por Paul Hsieh
• Uma apresentação do PowerPoint que demonstra como funciona a classificação por heap para educadores.
• Estruturas de dados abertas - Seção 11.1.3 - Heap-Sort , Pat Morin