Ordinamento heap in Java

1. Introduzione

In questo tutorial vedremo come funziona l'ordinamento heap e lo implementeremo in Java.

L'ordinamento dell'heap si basa sulla struttura dei dati dell'heap. Per comprendere correttamente l'ordinamento degli heap, esamineremo prima gli heap e come vengono implementati.

2. Struttura dei dati dell'heap

Un heap è una struttura dati specializzata basata su albero . Quindi è composto da nodi. Assegniamo gli elementi ai nodi: ogni nodo contiene esattamente un elemento.

Inoltre, i nodi possono avere figli. Se un nodo non ha figli, lo chiamiamo foglia.

Ciò che rende speciale Heap sono due cose:

  1. il valore di ogni nodo deve essere minore o uguale a tutti i valori memorizzati nei suoi figli
  2. è un albero completo , il che significa che ha la minore altezza possibile

A causa della prima regola, l'elemento minimo sarà sempre nella radice dell'albero .

Il modo in cui applichiamo queste regole dipende dall'implementazione.

Gli heap vengono generalmente utilizzati per implementare le code di priorità perché Heap è un'implementazione molto efficiente per estrarre l'elemento minimo (o massimo).

2.1. Varianti di heap

Heap ha molte varianti, tutte differiscono in alcuni dettagli di implementazione.

Ad esempio, quello che abbiamo descritto sopra è un Min-Heap, perché un genitore è sempre inferiore a tutti i suoi figli . In alternativa, avremmo potuto definire Max-Heap, nel qual caso un genitore è sempre maggiore dei suoi figli. Quindi, l'elemento più grande sarà nel nodo radice.

Possiamo scegliere tra molte implementazioni ad albero. Il più semplice è un albero binario. In un albero binario, ogni nodo può avere al massimo due figli. Li chiamiamo bambino sinistro e bambino destro .

Il modo più semplice per applicare la seconda regola è utilizzare un albero binario completo. Un albero binario completo segue alcune semplici regole:

  1. se un nodo ha un solo figlio, dovrebbe essere il figlio sinistro
  2. solo il nodo più a destra del livello più profondo può avere esattamente un figlio
  3. le foglie possono essere solo al livello più profondo

Vediamo queste regole con alcuni esempi:

 1 2 3 4 5 6 7 8 9 10 () () () () () () () () () () / \ / \ / \ / \ / \ / / / \ () () () () () () () () () () () () () () / \ / \ / \ / / \ () () () () () () () () () / ()

Gli alberi 1, 2, 4, 5 e 7 seguono le regole.

Gli alberi 3 e 6 violano la prima regola, 8 e 9 la seconda regola e 10 violano la terza regola.

In questo tutorial, ci concentreremo su Min-Heap con un'implementazione di albero binario .

2.2. Inserimento di elementi

Dovremmo implementare tutte le operazioni in un modo che mantenga gli invarianti Heap. In questo modo, possiamo costruire l'Heap con inserimenti ripetuti , quindi ci concentreremo sulla singola operazione di inserimento.

Possiamo inserire un elemento con i seguenti passaggi:

  1. crea una nuova foglia che è lo slot disponibile più a destra nel livello più profondo e memorizza l'elemento in quel nodo
  2. se l'elemento è minore di quello genitore, li scambiamo
  3. continuare con il passaggio 2, fino a quando l'elemento è inferiore a quello genitore o diventa la nuova radice

Nota, quel passaggio 2 non violerà la regola Heap, perché se sostituiamo il valore di un nodo con uno minore, sarà comunque inferiore ai suoi figli.

Vediamo un esempio! Vogliamo inserire 4 in questo Heap:

 2 / \ / \ 3 6 / \ 5 7

Il primo passo è creare una nuova foglia che memorizzi 4:

 2 / \ / \ 3 6 / \ / 5 7 4

Poiché 4 è inferiore al genitore, 6, li scambiamo:

 2 / \ / \ 3 4 / \ / 5 7 6

Ora controlliamo se 4 è inferiore a quello genitore o meno. Poiché il suo genitore è 2, ci fermiamo. L'heap è ancora valido e abbiamo inserito il numero 4.

Inseriamo 1:

 2 / \ / \ 3 4 / \ / \ 5 7 6 1

Dobbiamo scambiare 1 e 4:

 2 / \ / \ 3 1 / \ / \ 5 7 6 4

Ora dovremmo scambiare 1 e 2:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

Poiché 1 è la nuova radice, ci fermiamo.

3. Implementazione dell'heap in Java

Poiché utilizziamo un albero binario completo, possiamo implementarlo con un array : un elemento dell'array sarà un nodo dell'albero. Contrassegniamo ogni nodo con gli indici dell'array da sinistra a destra, dall'alto verso il basso nel modo seguente:

 0 / \ / \ 1 2 / \ / 3 4 5

L'unica cosa di cui abbiamo bisogno è tenere traccia di quanti elementi memorizziamo nell'albero. In questo modo l'indice del prossimo elemento che vogliamo inserire sarà la dimensione dell'array.

Usando questa indicizzazione, possiamo calcolare l'indice dei nodi padre e figlio:

  • genitore: (indice - 1) / 2
  • left child: 2 * index + 1
  • right child: 2 * index + 2

Since we don't want to bother with array reallocating, we'll simplify the implementation even more and use an ArrayList.

A basic Binary Tree implementation looks like this:

class BinaryTree { List elements = new ArrayList(); void add(E e) { elements.add(e); } boolean isEmpty() { return elements.isEmpty(); } E elementAt(int index) { return elements.get(index); } int parentIndex(int index) { return (index - 1) / 2; } int leftChildIndex(int index) { return 2 * index + 1; } int rightChildIndex(int index) { return 2 * index + 2; } }

The code above only adds the new element to the end of the tree. Therefore, we need to traverse the new element up if necessary. We can do it with the following code:

class Heap
    
      { // ... void add(E e) { elements.add(e); int elementIndex = elements.size() - 1; while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) { int parentIndex = parentIndex(elementIndex); swap(elementIndex, parentIndex); elementIndex = parentIndex; } } boolean isRoot(int index) { return index == 0; } boolean isCorrectChild(int index) { return isCorrect(parentIndex(index), index); } boolean isCorrect(int parentIndex, int childIndex) { if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) { return true; } return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0; } boolean isValidIndex(int index) { return index < elements.size(); } void swap(int index1, int index2) { E element1 = elementAt(index1); E element2 = elementAt(index2); elements.set(index1, element2); elements.set(index2, element1); } // ... }
    

Note, that since we need to compare the elements, they need to implement java.util.Comparable.

4. Heap Sort

Since the root of the Heap always contains the smallest element, the idea behind Heap Sort is pretty simple: remove the root node until the Heap becomes empty.

The only thing we need is a remove operation, which keeps the Heap in a consistent state. We must ensure that we don't violate the structure of the Binary Tree or the Heap property.

To keep the structure, we can't delete any element, except the rightmost leaf. So the idea is to remove the element from the root node and store the rightmost leaf in the root node.

But this operation will most certainly violate the Heap property. So if the new root is greater than any of its child nodes, we swap it with its least child node. Since the least child node is less than all other child nodes, it doesn't violate the Heap property.

We keep swapping until the element becomes a leaf, or it's less than all of its children.

Let's delete the root from this tree:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

First, we place the last leaf in the root:

 4 / \ / \ 3 2 / \ / 5 7 6

Then, since it's greater than both of its children, we swap it with its least child, which is 2:

 2 / \ / \ 3 4 / \ / 5 7 6

4 is less than 6, so we stop.

5. Heap Sort Implementation in Java

With all we have, removing the root (popping) looks like this:

class Heap
    
      { // ... E pop() { if (isEmpty()) { throw new IllegalStateException("You cannot pop from an empty heap"); } E result = elementAt(0); int lasElementIndex = elements.size() - 1; swap(0, lasElementIndex); elements.remove(lasElementIndex); int elementIndex = 0; while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) { int smallerChildIndex = smallerChildIndex(elementIndex); swap(elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } return result; } boolean isLeaf(int index) { return !isValidIndex(leftChildIndex(index)); } boolean isCorrectParent(int index) { return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index)); } int smallerChildIndex(int index) { int leftChildIndex = leftChildIndex(index); int rightChildIndex = rightChildIndex(index); if (!isValidIndex(rightChildIndex)) { return leftChildIndex; } if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) { return leftChildIndex; } return rightChildIndex; } // ... }
    

Like we said before, sorting is just creating a Heap, and removing the root repeatedly:

class Heap
    
      { // ... static 
     
       List sort(Iterable elements) { Heap heap = of(elements); List result = new ArrayList(); while (!heap.isEmpty()) { result.add(heap.pop()); } return result; } static 
      
        Heap of(Iterable elements) { Heap result = new Heap(); for (E element : elements) { result.add(element); } return result; } // ... }
      
     
    

We can verify it's working with the following test:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() { // given List elements = Arrays.asList(3, 5, 1, 4, 2); // when List sortedElements = Heap.sort(elements); // then assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5)); }

Note, that we could provide an implementation, which sorts in-place, which means we provide the result in the same array we got the elements. Additionally, this way we don't need any intermediate memory allocation. However, that implementation would be a bit harder to understand.

6. Time Complexity

Heap sort consists of two key steps, inserting an element and removing the root node. Both steps have the complexity O(log n).

Since we repeat both steps n times, the overall sorting complexity is O(n log n).

Note, that we didn't mention the cost of array reallocation, but since it's O(n), it doesn't affect the overall complexity. Also, as we mentioned before, it's possible to implement an in-place sorting, which means no array reallocation is necessary.

Also worth mentioning, that 50% of the elements are leaves, and 75% of elements are at the two bottommost levels. Therefore, most insert operations won't take more, than two steps.

Si noti che sui dati del mondo reale, Quicksort è solitamente più performante di Heap Sort. Il lato positivo è che Heap Sort ha sempre una complessità temporale O (n log n) nel caso peggiore .

7. Conclusione

In questo tutorial, abbiamo visto un'implementazione di Binary Heap e Heap Sort.

Anche se la complessità temporale è O (n log n) , nella maggior parte dei casi, non è il miglior algoritmo sui dati del mondo reale.

Come al solito, gli esempi sono disponibili su GitHub.