O segundo método é o extract, que extrai o nó raiz e reconstrói o heap com N-1 elementos. O processo é repetido até que todos os nós sejam extraídos.

Exemplo 1_3_6: exemplo de busca heapSort.

private void extract() {
       int current, maxChildIndex;
    boolean done;
    for (int size = heap.length - 1; size >= 0; size--) {
        // remove o nó raiz
        sortedList[size] = heap[0];
        // move o último nó para o nó raiz
        heap[0] = heap[size];
        // reconstroi o heap com menos um elemento
        current = 0;
        done = false;
        while (!done) {
            if (2 * current + 1 > size) {
            // o nó atual não tem nó filho, então pára.
                    done = true;
            } else {
            // o nó atual tem pelo menos um nó filho
            // busca o índice do maior filho
                 maxChildIndex = maxChild(current, size);
                 if (heap[current] < heap[maxChildIndex]) {
                // se o filho for maior então troca e continua
                swap(current, maxChildIndex);
                current = maxChildIndex;
                  } else { // se todos os nós tiverem a condição 
                    // de valor satisfeita então para
                    done = true;
                }
              }
            }
            testPrint(size); // TEMP
        }
    }
Copyright © 2014 AIEC.