Сортиране на купчина в Java

Програмиране

1. Въведение

В този урок ще видим как работи Heap Sort и ще го внедрим в Java.

Heap Sort се основава на структурата на данните Heap. За да разберем правилно сортирането на купчините, първо ще разгледаме купчините и как те се прилагат.

2. Структура на данните от купчината

A Heap е специализирана структура на данни, базирана на дърво . Следователно той е съставен от възли. Присвояваме елементите на възли: всеки възел съдържа точно един елемент.

Също така възлите могат да имат деца. Ако възел няма деца, ние го наричаме лист.

Това, което Heap прави специално, са две неща:

  1. стойността на всеки възел трябва да бъде по-малка или равна на всички стойности, съхранявани в неговите дъщери
  2. това е цяло дърво , което означава, че има най-малката възможна височина

Поради 1-вото правило, най-малкото елемент винаги ще бъде в корена на дървото .

Начинът, по който прилагаме тези правила, зависи от изпълнението.

Обикновено купчините се използват за реализиране на приоритетни опашки, защото Heap е много ефективно изпълнение на извличане на най-малкия (или най-големия) елемент.

2.1. Варианти на купчина

Heap има много варианти, всички те се различават в някои подробности за изпълнението.

Например това, което описахме по-горе, е Min-Heap, защото родителят винаги е по-малък от всичките му деца . Като алтернатива бихме могли да дефинираме Max-Heap, като в този случай родителят винаги е по-голям от децата. Следователно, най-големият елемент ще бъде в основния възел.

Можем да избираме от много изпълнения на дървета. Най-директното е двоично дърво. В двоично дърво всеки възел може да има най-много две деца. Ние ги наричаме ляво дете и дясно дете .

Най-лесният начин да се приложи второто правило е да се използва пълно двоично дърво. Пълното двоично дърво следва някои прости правила:

  1. ако възел има само едно дете, това трябва да е лявото му дете
  2. само най-десният възел на най-дълбокото ниво може да има точно едно дете
  3. листата могат да бъдат само на най-дълбокото ниво

Нека да видим тези правила с няколко примера:

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

Дърветата 1, 2, 4, 5 и 7 спазват правилата.

Дърво 3 и 6 нарушават 1-во правило, 8 и 9 2-ро правило, а 10 нарушават 3-то правило.

В този урок ще се съсредоточим върху Min-Heap с изпълнение на двоично дърво .

2.2. Вмъкване на елементи

Трябва да приложим всички операции по начин, който да запази инвариантите на Heap. По този начин можем да изградим Heap с повтарящи се вмъквания , така че ще се съсредоточим върху операцията с едно вмъкване.

Можем да вмъкнем елемент със следните стъпки:

  1. създайте нов лист, който е най-десният наличен слот на най-дълбокото ниво и съхранявайте елемента в този възел
  2. ако елементът е по-малък от родителския, ние ги разменяме
  3. продължете със стъпка 2, докато елементът е по-малък от своя родител или стане новият корен

Обърнете внимание, че стъпка 2 няма да наруши правилото Heap, защото ако заменим стойността на възел с по-малко, то пак ще бъде по-малко от неговите деца.

Да видим пример! Искаме да вмъкнем 4 в тази купчина:

 2 / \ / \ 3 6 / \ 5 7

Първата стъпка е да се създаде нов лист, който съхранява 4:

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

Тъй като 4 е по-малко, отколкото е родител, 6, ние ги разменяме:

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

Сега проверяваме дали 4 е по-малко, отколкото е родител или не. Тъй като родителят му е 2, спираме. Heap все още е валиден и ние вмъкнахме номер 4.

Нека вмъкнем 1:

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

Трябва да разменяме 1 и 4:

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

Сега трябва да разменяме 1 и 2:

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

Тъй като 1 е новият корен, спираме.

3. Внедряване на купчина в Java

Тъй като използваме пълно двоично дърво, можем да го реализираме с масив : елемент в масива ще бъде възел в дървото. Маркираме всеки възел с индексите на масива отляво надясно, отгоре надолу по следния начин:

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

Единственото нещо, от което се нуждаем, е да следим колко елементи съхраняваме в дървото. По този начин индексът на следващия елемент, който искаме да вмъкнем, ще бъде размерът на масива.

Използвайки това индексиране, можем да изчислим индекса на родителския и дъщерния възел:

  • родител: (индекс - 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.

Имайте предвид, че при реални данни Quicksort обикновено е по-ефективен от Heap Sort. Сребърната облицовка е, че Heap Sort винаги има най-лошия случай на O (n log n) времева сложност.

7. Заключение

В този урок видяхме изпълнение на Binary Heap и Heap Sort.

Въпреки че сложността на времето е O (n log n) , в повечето случаи това не е най-добрият алгоритъм за реални данни.

Както обикновено, примерите са достъпни в GitHub.