Heapsortering i Java

1. Introduktion

I den här handledningen ser vi hur Heap Sort fungerar och vi implementerar det i Java.

Heap Sort baseras på Heap-datastrukturen. För att förstå Heap Sort ordentligt gräver vi först in Heaps och hur de implementeras.

2. Heapdatastruktur

A Heap är en specialiserad trädbaserad datastruktur . Därför består den av noder. Vi tilldelar elementen till noder: varje nod innehåller exakt ett element.

Noder kan också ha barn. Om en nod inte har några barn kallar vi det blad.

Vad Heap gör speciellt är två saker:

  1. varje nods värde måste vara mindre eller lika med alla värden som lagras i sina barn
  2. det är ett komplett träd , vilket betyder att det har minsta möjliga höjd

På grund av den första regeln kommer alltid det minsta elementet att finnas i trädets rot .

Hur vi tillämpar dessa regler är implementeringsberoende.

Heaps används vanligtvis för att implementera prioritetsköer eftersom Heap är en mycket effektiv implementering av att extrahera det minsta (eller största) elementet.

2.1. Heapvarianter

Heap har många varianter, alla skiljer sig åt i vissa implementeringsdetaljer.

Till exempel, vad vi beskrev ovan är en Min-Heap, eftersom en förälder alltid är mindre än alla sina barn . Alternativt kunde vi ha definierat Max-Heap, i vilket fall en förälder alltid är större än sina barn. Därför kommer det största elementet att finnas i rotnoden.

Vi kan välja mellan många trädimplementeringar. Det enklaste är ett binärt träd. I ett binärt träd kan varje nod ha högst två barn. Vi kallar dem vänster barn och höger barn .

Det enklaste sättet att genomdriva den andra regeln är att använda ett fullständigt binärt träd. Ett fullständigt binärt träd följer några enkla regler:

  1. om en nod bara har ett barn, bör det vara dess vänstra barn
  2. endast noden längst till höger på den djupaste nivån kan ha exakt ett barn
  3. löv kan bara vara på den djupaste nivån

Låt oss se dessa regler med några exempel:

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

Träden 1, 2, 4, 5 och 7 följer reglerna.

Träd 3 och 6 bryter mot den första regeln, 8 och 9 den andra regeln och 10 bryter mot den tredje regeln.

I den här handledningen fokuserar vi på Min-Heap med en implementering av binärt träd .

2.2. Infoga element

Vi bör genomföra alla operationer på ett sätt som håller Heap-invarianterna. På det här sättet kan vi bygga Heap med upprepade insättningar , så vi fokuserar på operationen med en enda insats.

Vi kan infoga ett element med följande steg:

  1. skapa ett nytt blad som är den ledigaste platsen på den djupaste nivån och lagra objektet i den noden
  2. om elementet är mindre än det är förälder byter vi dem
  3. fortsätt med steg 2 tills elementet är mindre än det är förälder eller det blir den nya roten

Observera att steg 2 inte bryter mot Heap-regeln, för om vi ersätter en nods värde med en mindre, kommer det fortfarande att vara mindre än det är barn.

Låt oss se ett exempel! Vi vill infoga 4 i denna hög:

 2 / \ / \ 3 6 / \ 5 7

Det första steget är att skapa ett nytt blad som lagrar 4:

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

Eftersom 4 är mindre än dess förälder, 6, byter vi dem:

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

Nu kontrollerar vi om 4 är mindre än det är förälder eller inte. Eftersom föräldern är 2 stannar vi. Heapen är fortfarande giltig och vi införde nummer 4.

Låt oss infoga 1:

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

Vi måste byta 1 och 4:

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

Nu ska vi byta 1 och 2:

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

Eftersom 1 är den nya roten slutar vi.

3. Heapimplementering i Java

Eftersom vi använder ett fullständigt binärt träd kan vi implementera det med en matris : ett element i matrisen kommer att vara en nod i trädet. Vi markerar varje nod med matrisindexen från vänster till höger, från topp till botten på följande sätt:

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

Det enda vi behöver är att hålla reda på hur många element vi lagrar i trädet. På så sätt kommer indexet för nästa element som vi vill infoga att vara storleken på matrisen.

Med hjälp av denna indexering kan vi beräkna indexet på föräldra- och barnnoder:

  • förälder: (index - 1) / 2
  • vänster barn: 2 * index + 1
  • höger barn: 2 * index + 2

Eftersom vi inte vill bry oss om arrayfördelning förenklar vi implementeringen ännu mer och använder en ArrayList .

En grundläggande implementering av binärt träd ser ut så här:

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

Koden ovan lägger bara till det nya elementet i slutet av trädet. Därför måste vi gå igenom det nya elementet om det behövs. Vi kan göra det med följande kod:

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); } // ... }
    

Observera att eftersom vi behöver jämföra elementen måste de implementera java.util.Comparable .

4. Högsortering

Eftersom roten till högen alltid innehåller det minsta elementet är tanken bakom högsorteringen ganska enkel: ta bort rotnoden tills högen blir tom .

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.

Observera att Quicksort på verkliga data vanligtvis är mer prestanda än Heap Sort. Silverfodret är att Heap Sort alltid har en värsta fall O (n log n) tidskomplexitet.

7. Slutsats

I denna handledning såg vi en implementering av Binary Heap and Heap Sort.

Även om det är tidskomplexitet är O (n log n) , är det i de flesta fall inte den bästa algoritmen för verkliga data.

Som vanligt finns exemplen tillgängliga på GitHub.