자바의 힙 정렬

1. 소개

이 자습서에서는 힙 정렬이 어떻게 작동하는지 살펴보고 Java로 구현합니다.

힙 정렬은 힙 데이터 구조를 기반으로합니다. 힙 정렬을 제대로 이해하기 위해 먼저 힙과 힙이 구현되는 방법을 살펴 보겠습니다.

2. 힙 데이터 구조

힙은 특수 트리 기반 데이터 구조 입니다. 따라서 노드로 구성됩니다. 요소를 노드에 할당합니다. 모든 노드는 정확히 하나의 요소를 포함합니다.

또한 노드는 자식을 가질 수 있습니다. 노드에 자식이 없으면 리프라고합니다.

힙이 특별하게 만드는 것은 두 가지입니다.

  1. 모든 노드의 값은 하위에 저장된 모든 값보다 작거나 같아야합니다.
  2. 그것은 완전한 나무 입니다. 즉, 가능한 최소한의 높이를 가지고 있습니다.

첫 번째 규칙 때문에 최소 요소는 항상 트리의 루트에 있습니다.

이러한 규칙을 시행하는 방법은 구현에 따라 다릅니다.

힙은 최소 (또는 최대) 요소를 추출하는 매우 효율적인 구현이므로 일반적으로 우선 순위 큐를 구현하는 데 사용됩니다.

2.1. 힙 변형

힙에는 많은 변형이 있으며 모두 일부 구현 세부 사항이 다릅니다.

예를 들어 위에서 설명한 것은 Min-Heap입니다. 부모는 항상 모든 자식보다 작기 때문 입니다. 또는 Max-Heap을 정의 할 수 있습니다.이 경우 부모는 항상 자식보다 큽니다. 따라서 가장 큰 요소는 루트 노드에 있습니다.

많은 트리 구현 중에서 선택할 수 있습니다. 가장 간단한 것은 이진 트리입니다. 이진 트리에서 모든 노드는 최대 두 개의 자식을 가질 수 있습니다. 우리는 그들이 전화를 아이 좌측우측 아이 .

두 번째 규칙을 적용하는 가장 쉬운 방법은 Full Binary Tree를 사용하는 것입니다. 전체 바이너리 트리는 몇 가지 간단한 규칙을 따릅니다.

  1. 노드에 자식이 하나만있는 경우 왼쪽 자식이어야합니다.
  2. 가장 깊은 수준의 맨 오른쪽 노드 만 정확히 하나의 자식을 가질 수 있습니다.
  3. 잎은 가장 깊은 수준에만있을 수 있습니다.

몇 가지 예를 통해 이러한 규칙을 살펴 보겠습니다.

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

나무 1, 2, 4, 5 및 7은 규칙을 따릅니다.

트리 3과 6은 첫 번째 규칙, 8과 9는 두 번째 규칙, 10은 세 번째 규칙을 위반합니다.

이 튜토리얼에서는 바이너리 트리 구현 이있는 Min-Heap에 중점을 둘 것입니다.

2.2. 요소 삽입

힙을 불변으로 유지하는 방식으로 모든 작업을 구현해야합니다. 이런 식 으로 반복 삽입으로 힙을 빌드 할 수 있으므로 단일 삽입 작업에 초점을 맞출 것입니다.

다음 단계에 따라 요소를 삽입 할 수 있습니다.

  1. 가장 깊은 수준에서 가장 오른쪽에있는 슬롯 인 새 리프를 만들고 해당 노드에 항목을 저장합니다.
  2. 요소가 부모보다 작 으면 교체합니다.
  3. 요소가 상위 요소보다 작거나 새 루트가 될 때까지 2 단계를 계속합니다.

2 단계는 힙 규칙을 위반하지 않습니다. 노드 값을 더 작은 값으로 바꾸면 여전히 하위 값보다 작기 때문입니다.

예를 봅시다! 이 힙에 4를 삽입하려고합니다.

 2 / \ / \ 3 6 / \ 5 7

첫 번째 단계는 4를 저장하는 새 리프를 만드는 것입니다.

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

4는 상위 6보다 작으므로 다음과 같이 바꿉니다.

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

이제 4가 부모보다 작은 지 확인합니다. 부모가 2이므로 중지합니다. 힙은 여전히 ​​유효하며 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. 자바에서 힙 구현

Full Binary Tree를 사용하기 때문에 배열로 구현할 수 있습니다. 배열 의 요소는 트리의 노드가됩니다. 다음과 같은 방식으로 왼쪽에서 오른쪽, 위에서 아래로 배열 인덱스로 모든 노드를 표시합니다.

 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는 일반적으로 힙 정렬보다 성능이 뛰어납니다. 실버 라이닝은 힙 정렬이 항상 최악의 경우 O (n log n) 시간 복잡도를 갖는다는 것입니다.

7. 결론

이 자습서에서는 이진 힙 및 힙 정렬의 구현을 보았습니다.

시간 복잡성이 O (n log n) 이지만 대부분의 경우 실제 데이터에 대한 최상의 알고리즘은 아닙니다.

평소처럼 예제는 GitHub에서 사용할 수 있습니다.