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 } }