Heap Sort in Java

1. Einleitung

In diesem Tutorial werden wir sehen, wie Heap Sort funktioniert, und wir werden es in Java implementieren.

Die Heap-Sortierung basiert auf der Heap-Datenstruktur. Um die Heap-Sortierung richtig zu verstehen, werden wir uns zunächst mit Heaps und deren Implementierung befassen.

2. Heap-Datenstruktur

Ein Heap ist eine spezialisierte baumbasierte Datenstruktur . Daher besteht es aus Knoten. Wir ordnen die Elemente Knoten zu: Jeder Knoten enthält genau ein Element.

Knoten können auch untergeordnete Elemente haben. Wenn ein Knoten keine Kinder hat, nennen wir ihn Blatt.

Was Heap so besonders macht, sind zwei Dinge:

  1. Der Wert jedes Knotens muss kleiner oder gleich allen Werten sein, die in seinen untergeordneten Knoten gespeichert sind
  2. Es ist ein vollständiger Baum , was bedeutet, dass er die geringstmögliche Höhe hat

Aufgrund der 1. Regel befindet sich das kleinste Element immer in der Wurzel des Baums .

Wie wir diese Regeln durchsetzen, hängt von der Implementierung ab.

Heaps werden normalerweise zum Implementieren von Prioritätswarteschlangen verwendet, da Heap eine sehr effiziente Implementierung zum Extrahieren des kleinsten (oder größten) Elements ist.

2.1. Heap-Varianten

Heap hat viele Varianten, die sich alle in einigen Implementierungsdetails unterscheiden.

Was wir oben beschrieben haben, ist beispielsweise ein Min-Heap, da ein Elternteil immer kleiner ist als alle seine Kinder . Alternativ hätten wir Max-Heap definieren können. In diesem Fall ist ein Elternteil immer größer als seine Kinder. Daher befindet sich das größte Element im Wurzelknoten.

Wir können aus vielen Baumimplementierungen auswählen. Am einfachsten ist ein Binärbaum. In einem Binärbaum kann jeder Knoten höchstens zwei untergeordnete Knoten haben. Wir nennen sie linkes Kind und rechtes Kind .

Der einfachste Weg, die 2. Regel durchzusetzen, ist die Verwendung eines vollständigen Binärbaums. Ein vollständiger Binärbaum folgt einigen einfachen Regeln:

  1. Wenn ein Knoten nur ein Kind hat, sollte dies sein linkes Kind sein
  2. Nur der Knoten ganz rechts auf der tiefsten Ebene kann genau ein Kind haben
  3. Blätter können nur auf der tiefsten Ebene sein

Sehen wir uns diese Regeln anhand einiger Beispiele an:

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

Die Bäume 1, 2, 4, 5 und 7 folgen den Regeln.

Baum 3 und 6 verletzen die 1. Regel, 8 und 9 die 2. Regel und 10 die 3. Regel.

In diesem Tutorial konzentrieren wir uns auf Min-Heap mit einer Binärbaum- Implementierung.

2.2. Elemente einfügen

Wir sollten alle Operationen so implementieren, dass die Heap-Invarianten erhalten bleiben. Auf diese Weise können wir den Heap mit wiederholten Einfügungen erstellen , sodass wir uns auf die einzelne Einfügeoperation konzentrieren.

Wir können ein Element mit den folgenden Schritten einfügen:

  1. Erstellen Sie ein neues Blatt, das der am weitesten rechts verfügbare Steckplatz auf der tiefsten Ebene ist, und speichern Sie das Element in diesem Knoten
  2. Wenn das Element kleiner als das übergeordnete Element ist, tauschen wir sie aus
  3. Fahren Sie mit Schritt 2 fort, bis das Element kleiner als das übergeordnete Element ist oder zur neuen Wurzel wird

Beachten Sie, dass Schritt 2 nicht gegen die Heap-Regel verstößt, denn wenn wir den Wert eines Knotens durch einen kleineren ersetzen, ist er immer noch kleiner als seine untergeordneten Werte.

Sehen wir uns ein Beispiel an! Wir wollen 4 in diesen Heap einfügen:

 2 / \ / \ 3 6 / \ 5 7

Der erste Schritt besteht darin, ein neues Blatt zu erstellen, in dem 4 gespeichert sind:

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

Da 4 kleiner ist als die Eltern, 6, tauschen wir sie aus:

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

Jetzt prüfen wir, ob 4 kleiner als das übergeordnete Element ist oder nicht. Da sein Elternteil 2 ist, hören wir auf. Der Heap ist noch gültig und wir haben Nummer 4 eingefügt.

Fügen wir 1 ein:

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

Wir müssen 1 und 4 tauschen:

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

Jetzt sollten wir 1 und 2 tauschen:

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

Da 1 die neue Wurzel ist, hören wir auf.

3. Heap-Implementierung in Java

Da wir einen vollständigen Binärbaum verwenden, können wir ihn mit einem Array implementieren : Ein Element im Array ist ein Knoten im Baum. Wir markieren jeden Knoten mit den Array-Indizes von links nach rechts und von oben nach unten auf folgende Weise:

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

Das einzige, was wir brauchen, ist zu verfolgen, wie viele Elemente wir im Baum speichern. Auf diese Weise entspricht der Index des nächsten Elements, das wir einfügen möchten, der Größe des Arrays.

Mit dieser Indizierung können wir den Index der übergeordneten und untergeordneten Knoten berechnen:

  • Elternteil: (Index - 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.

Beachten Sie, dass Quicksort in realen Daten normalerweise leistungsfähiger ist als Heap Sort. Der Silberstreifen ist, dass Heap Sort immer eine O (n log n) -Zeitkomplexität im ungünstigsten Fall aufweist .

7. Fazit

In diesem Tutorial haben wir eine Implementierung von Binary Heap und Heap Sort gesehen.

Obwohl die Zeitkomplexität O (n log n) ist , ist sie in den meisten Fällen nicht der beste Algorithmus für reale Daten.

Wie üblich sind die Beispiele auf GitHub verfügbar.