어느 가게에 손님이 몰렸다고 해봅시다. 그러면 손님들에게 대기 순번을 나눠줬다가, 여유가 생길 때마다 다음 손님을 받는 것으로 해결하게 됩니다.

이것이 프로그래밍 과제로 주어졌다고 상상한다면, 다음과 같은 데이터 구조data structure를 떠올릴 수 있습니다.

• add(): 대기 순번을 추가합니다.

• poll(): 다음 대기 순번을 가져옵니다.

보통은 먼저 대기하던 손님부터 차례대로 받고 싶을 것입니다. 즉 add()로 추가한 순서대로 poll() 연산이 순번을 가져오는 것입니다. 이런 데이터 구조는 FIFOfirst-in first-out 순서를 따르는 큐queue라고 부릅니다.

그런데 단골 손님을 우선 받으려고 한다면 어떨까요? 즉 add()로 추가할 때 임의로 우선순위를 부여하고, poll()로 가장 우선순위가 높은 것부터 꺼내는 것입니다.

이런 연산을 갖는 큐를 우선순위 큐priority queue라고 부릅니다. 따라서 우선순위 큐는 FIFO 큐를 일반화 한 것으로 볼 수 있습니다.

그렇다면 우선순위 큐는 어떻게 만들 수 있을까요? 어떤 데이터 구조에 가장 큰 것을 찾는 getMax() 연산 같은 것이 있다면, 이것만으로도 우선순위 큐를 만들기 충분해집니다. 왜냐면 getMax()로 가장 큰 우선순위를 찾는 것이 곧 poll() 연산이기 때문입니다.

한번 getMax()를 갖는 데이터 구조를 만들어 봅시다. 가장 큰 값을 항상 루트 노드root node에 두는 트리를 생각해본다면, poll() 연산은 루트 노드의 값을 가져오는 것에 불과하게 됩니다.

그러면 가장 큰 값이 항상 루트 노드에 있도록 정리하는 것이 관건입니다. 이를 위해, 모든 노드가 그 자식 노드 이상이 되게끔 둔다고 해봅시다. 이런 트리는 힙 프로퍼티heap property를 갖는다고 부르거나, 힙 오더heap-ordered로 정리되어 있다고 합니다. 특히 부모 노드가 자식 노드 이상이어서 루트 노드가 가장 큰 값이 되는 경우, 맥스 힙 프로퍼티max-heap property라고도 부릅니다.

한편, 트리라는 데이터 구조를 자주 언급할 것이므로 용어를 간략히 정리해보겠습니다.

• 자식 노드가 없는 것을 리프leaf 노드라고 하고, 리프 노드를 제외한 모든 노드를 인터널internal 노드라고 부릅니다.

• 각 노드에는 루트 노드까지의 경로가 존재합니다. 그 길이를 노드의 깊이depth라고 합니다. 반대 방향으로, 그 노드에서 리프 노드까지의 경로도 존재합니다. 그 중 가장 긴 것을 노드의 높이height라고 합니다.

• 트리의 높이는 루트 노드의 높이를 일컫습니다. 트리의 레벨level이란, 깊이가 같은 노드들을 말합니다. 예를 들어 레벨 0은 루트 노드를 말하고, 레벨 1은 그 자식 노드들이 됩니다.

• 각 노드가 최대 두 개의 자식 노드를 가지는 트리를 바이너리 트리binary tree라고 부릅니다. 여기서 인터널 노드가 모두 자식 노드를 두 개씩 갖고, 리프 노드가 같은 깊이를 가지면, 그 트리는 컴플리트complete하다고 부릅니다. 이런 트리는 다이어그램 상 세모를 채우는 꼴로 나타납니다. 여기서는 의미를 좀더 확장해서, 마지막 레벨에서 오른쪽이 일부 빈 경우도 컴플리트하다고 하겠습니다.

힙heap은 힙 프로퍼티를 가지는 컴플리트 트리를 말합니다. 그 중 바이너리 힙binary heap은 바이너리 트리를 이용한 것을 말합니다. 트리가 컴플리트하기 때문에, 노드가 채워지는 순서로 인덱스를 매기면 배열로 트리를 표현할 수 있게 됩니다.

이렇게 맥스 힙 프로퍼티를 만족시키는 힙은 맥스 힙max heap이라고 부릅니다. 앞으로의 내용을 통해, 이 데이터 구조가 우선순위 큐를 만드는 것 외의 여러 문제도 해결한다는 것을 알게 될 것입니다.

• 대표적으로는 소팅 알고리즘sorting algorithm으로서, 가장 큰 것을 계속해서 찾아 반대 순서로 두면 소트가 됩니다. 힙소트heapsort라고도 부릅니다.

• 소트된 데이터셋dataset이 여러 개가 주어질 때, 소트된 하나로 합치는 멀티웨이 머지multiway merge를 구현할 수 있습니다. 머지 소트merge sort의 쓰이는 머지의 일반화로도 볼 수 있는데, 우선순위 큐로 간단히 만들 수 있습니다.

바이너리 힙

컴플리트 바이너리 트리를 배열로 표현하고 힙 프로퍼티를 갖게하면 곧 바이너리 힙이 됩니다. 그러면 이 두 단계를 나눠서 살펴봅시다. 여기서 앞으로 트리라는 표현은 편의상 컴플리트 바이너리 트리를 일컫도록 하겠습니다.

배열로 만드는 트리

트리는 다음과 같은 ADT로 정의할 수 있습니다. 트리를 배열로 표현한다는 것은, 이 연산을 배열로 구현한다는 것입니다.

• getParent(node): node의 부모 노드를 구합니다.

• getLeftChild(node): node의 왼쪽 자식 노드를 구합니다.

• getRightChild(node): node의 오른쪽 자식 노드를 구합니다.

여기서 트리의 루트 노드가 배열 상 0의 인덱스를 갖는다고 해봅시다. 그러면 레벨 1은 인덱스를 1부터, 레벨 2는 3부터 가집니다. 즉 레벨 $n$는 $2^n-1$부터 갖게 됩니다.

노드를 인덱스로 표현한다면, 부모와 자식 노드를 얻는 것은 인덱스를 계산하는 일과 같습니다.

먼저, 트리에서 각 레벨의 가장 왼쪽 노드를 바라봅시다. 그러면 이 노드는 다음 레벨의 가장 왼쪽 노드를 자식 노드로 가집니다. 다시 말해, $2^n-1$은 $2^{n+1}-1$을 자식 노드로 갖습니다. 그리고 바로 오른쪽 노드인 $2^{n+1}$ 또한 자식 노드가 됩니다. 따라서 부모 노드를 구하는 함수는 다음과 같이 인덱스를 인덱스로 보내는 함수가 됩니다.

다음과 같이 함수 $f(n)$로도 표현할 수 있습니다.

여기서 $\lfloor x \rfloor$는 플로어 함수floor function로서, 소수점 이하를 버리기 위해 쓰인 것입니다. 사실 이 함수는 가장 왼쪽 노드 뿐만 아니라 나머지 노드에 대해서도 부모 노드를 구합니다. 따라서, 부모 노드를 구하는 getParent() 연산은 다음 수도코드와 같습니다.

이 연산을 거꾸로 하면 자식 노드를 구하는 연산이 됩니다. 먼저, 왼쪽 자식의 경우는 이렇게 만들 수 있습니다.

그리고 여기서 하나 더 큰 것을 리턴하면 오른쪽 자식이 됩니다.

힙 프로퍼티 유지하기

이제 어떤 배열이 주어지면, 어떤 트리를 표현한 것으로 바라볼 수 있습니다. 하지만 힙 프로퍼티가 없을 수도 있으니, 꼭 힙을 표현한 것이라고는 할 수 없습니다.

따라서 트리가 힙 오더를 따르도록 만들 필요가 있습니다. 만약 어떤 노드가 힙 오더를 따르지 않는다면, 가능성은 둘 중 하나입니다.

1. 그 부모 노드와 힙 오더를 따르지 않는다.

2. 그 자식 노드와 힙 오더를 따르지 않는다.

따라서 각각의 경우를 해결해봅시다.

첫 번째 경우, 부모 노드를 따라 올라가며 필요할 때마다 자리를 바꿉니다. 이 연산에는 버블 업bubble up, 스윔swim 등의 여러 이름이 붙어있지만, 여기서는 시프트 업sift up이라고 부르겠습니다.

이 연산은 다음 수도코드처럼 표현할 수 있습니다.

트리의 높이는 노드가 $n$ 개일 때 $\lfloor \log_2(n) \rfloor$이고, 시프트 업은 최악의 경우 높이만큼 반복하므로 $\Theta(\lg n)$의 시간이 든다는 것을 알 수 있습니다.

반면 두 번째 경우, 반대로 자식 노드를 따라 내려가며 자리를 바꿉니다. 이 때 더 큰 값을 가진 자식과 바꿔야 힙 오더를 유지할 수 있습니다. (이유는 직접 확인해보세요.)

이를 수행하는 시프트 다운sift down 연산은 다음과 같이 만들 수 있습니다.

이때에도 최악의 경우 $\Theta(\lg n)$의 시간 복잡도를 가집니다.

이렇게 만든 연산은 트리가 힙 프로퍼티를 잃게 되는 경우, 다시 힙 프로퍼티를 갖게 만들기 위해 쓰일 수 있습니다. 그 구체적인 예는 우선순위 큐를 구현할 때 볼 것입니다.

자바로 구현하기

먼저 배열을 트리로 표현하기 위해, 배열에서 부모와 자식 노드를 구하는 연산을 만들어봅시다. 간단한 인덱스 연산에 불과하지만, 배열을 추상적인 트리로서 바라보기 위해 별도의 클래스로 만들어보겠습니다.

class ArrayTree {
  private static int getParent(int index) {
    assert index >= 1;

    return (index-1)/2;
  }

  private static int getLeftChild(int index) {
    assert index >= 0;

    return 2*index+1;
  }

  private static int getRightChild(int index) {
    assert index >= 0;

    return 2*index+2;
  }

  // ...
}

이렇게 만든 연산은 루트 노드가 인덱스 0에 있다고 가정한 것입니다. 만약 루트 노드가 다른 인덱스를 가진다면, 그 인덱스를 받도록 다음과 같이 확장할 수 있습니다.

  public static int getParent(int index, int root) {
    assert root >= 0;

    return getParent(index-root) + root;
  }

  public static int getLeftChild(int index, int root) {
    assert root >= 0;

    return getLeftChild(index-root) + root;
  }

  public static int getRightChild(int index, int root) {
    assert root >= 0;

    return getRightChild(index-root) + root;
  }

이를 통해 시프트 업과 시프트 다운을 만들어봅시다. 여기서는 힙을 표현하는 데이터 구조를 배열에만 한정시키지 않고, 인덱스로 값을 가져오거나 줄 수 있는 모든 데이터 구조로 일반화 할 것입니다. 그런 인덱스 연산을 get과 set으로 받아 초기화하도록 만듭니다. 비교 연산 comp 또한 외부에서 받습니다.

public class Heapifier<T> {
  private Function<Integer, T> get;
  private BiConsumer<Integer, T> set;
  private Comparator<T> comp;

  public Heapifier(Function<Integer, T> get, BiConsumer<Integer, T> set, Comparator<T> comp) {
    this.get = get;
    this.set = set;
    this.comp = comp;
  }

  // ...
}

이어서 시프트 업은 다음과 같이 수도코드를 그대로 옮겨 만들 수 있습니다. 다만 배열의 루트 노드 인덱스 root는 외부에서 받습니다.

  public void siftUp(int index, int root) {
    while (index > root) {
      int parent = getParent(index, root);
      if (isHeapOrdered(parent, index)) {
        break;
      }

      this.swap(index, parent);
      index = parent;
    }
  }

여기서 힙 오더를 따르는지 확인하는 메소드는 이렇게 부모와 자식을 비교합니다.

  private boolean isHeapOrdered(int parentIndex, int childIndex) {
    T parent = this.get.apply(parentIndex);
    T child = this.get.apply(childIndex);
    return isGreaterThanOrEqualTo(parent, child, this.comp);
  }

여기서 쓰인 isGreasterThanOrEqualTo() 메소드는 편의상 별도로 분리한 것입니다.

  public static <T> boolean isGreaterThanOrEqualTo(T source, T target, Comparator<T> comparator) {
    return comparator.compare(source, target) >= 0;
  }

노드의 스왑을 위한 swap() 메소드는 get과 set을 통해 만듭니다.

  private void swap(int i, int j) {
    T temp = this.get.apply(i);
    this.set.accept(i, this.get.apply(j));
    this.set.accept(j, temp);
  }

한편, 시프트 다운은 다음과 같이 수도코드를 옮겨 만들 수 있습니다. 여기서 루트 노드와 마지막 노드의 인덱스를 각각 root와 last로 받습니다.

  public void siftDown(int index, int root, int last) {
    while (getLeftChild(index, root) <= last) {
      int largerChild = this.getLargerChildIndex(index, root, last);
      if (isHeapOrdered(index, largerChild)) {
        break;
      }

      this.swap(index, largerChild);
      index = largerChild;
    }
  }

다음 메소드는 둘 중 더 큰 자식 노드를 구합니다.

  private int getLargerChildIndex(int index, int root, int last) {
    int left = getLeftChild(index, root);
    assert left <= last;

    // return left child if no right one
    int right = getRightChild(index, root);
    if (right > last) {
      return left;
    }

    T leftValue = this.get.apply(left);
    T rightValue = this.get.apply(right);
    if (isGreaterThanOrEqualTo(leftValue, rightValue, this.comp)) {
      return left;
    } else {
      return right;
    }
  }

이렇게 만든 메소드는 다음과 같은 테스트 코드처럼 사용할 수 있습니다.

  @Test
  public void testGetParentAndGetChild() {
    int root = 42;
    int leftChild = ArrayTree.getLeftChild(root, root);
    int rightChild = ArrayTree.getRightChild(root, root);

    assertEquals(root, ArrayTree.getParent(leftChild, root));
    assertEquals(root, ArrayTree.getParent(rightChild, root));
  }

이 테스트 코드는 루트 노드의 인덱스가 무슨 값이더라도 통과합니다. 그리고 루트 노드가 주어지기만 하면 노드가 인덱스라는 사실을 신경쓰지 않을 수 있습니다. 즉 노드를 불투명한 값opaque value으로 취급할 수 있는 것입니다. 따라서 배열을 트리라는 데이터 구조로 추상화할 수 있게 됩니다.

우선순위 큐

처음에 언급한 것처럼, 우선순위 큐는 add()와 poll() 연산으로 정의했습니다. 여기서 add()` 연산은 시프트 업으로 만들 수 있습니다. 즉 새 데이터를 마지막 리프 노드로 추가한 뒤에, 시프트 업으로 정리해 힙 오더를 따르도록 만듭니다.

poll() 연산은 시프트 다운으로 만들 수 있습니다. 마지막 리프 노드를 루트 노드에 둔 뒤 시프트 다운으로 정리하면 힙 프로퍼티가 유지됩니다.

add()와 poll()은 각각 시프트 업과 시프트 다운의 시간 복잡도를 따릅니다. 즉 값의 개수 $n$에 대해, 둘 다 최악의 경우 $\Theta(\lg n)$의 시간이 듭니다.

자바로 구현하기

우선순위 큐가 가질 연산을 큐 인터페이스로 만들어봅시다.

public interface Queue<T> {
  public void add(T data);
  public T poll();
  public T peek();
  public int getSize();
  public boolean isEmpty();
}

여기서 peek()는 poll() 처럼 값을 가져오는 대신, 힙에서 꺼내지는 않습니다. getSize()는 큐에 든 데이터의 개수를, isEmpty()은 큐가 비어있는지 여부를 라턴합니다.

이제 힙으로 구현하는 우선순위 큐 클래스를 만듭시다. 내부적으로 사용할 배열은 크기를 알아서 조절할 것입니다. 여기서는 이전 글에서 만든 다이나믹 배열dynamic array를 가져다 쓰겠습니다.

public class HeapPriorityQueue<T> implements Queue<T> {
  private DynamicArray<T> arr;
  private Comparator<T> comp;
  private Heapifier<T> heapifier;

  public HeapPriorityQueue(Comparator<T> comp) {
    this.arr = new DynamicArray<>();
    this.comp = comp;
    this.heapifier = new Heapifier<>(this.arr::get, this.arr::set, this.comp);
  }

  // ...
}

이어서 add()와 poll() 연산은 수도코드를 그대로 옮겨 만듭니다.

  public void add(T value) {
    this.arr.append(value);
    this.heapifier.siftUp(this.arr.getSize()-1, 0);
  }

  public T poll() {
    T polled = this.arr.get(0);

    this.swap(0, this.arr.getSize()-1);
    this.arr.remove();
    this.heapifier.siftDown(0, 0, this.arr.getSize()-1);

    return polled;
  }

  private void swap(int i, int j) {
    T temp = this.arr.get(i);
    this.arr.set(i, this.arr.get(j));
    this.arr.set(j, temp);
  }

나머지 peek(), getSize(), isEmpty() 메소드는 구현이 간단하므로 직접 해보는 것으로 남기겠습니다.

소요 시간 측정

이제 add()와 poll() 메소드의 소요 시간을 재봅시다. 이론적으로는 최악의 경우 $\Theta(\lg n)$의 시간이 든다고 분석했습니다.

다음은 $n$ 개의 값을 우선순위 큐에 add()로 추가한 경우와, 그렇게 추가하고 모두 poll()로 꺼낸 경우를 측정한 것입니다. 그러면 다음과 같이 이론적으로 최악의 경우 $\Theta(n \lg n)$의 시간 복잡도를 갖게됩니다.

여기서 $\lg (n!) \sim n \lg n$이라는 사실은 스털링 근사Stirling’s approximation로부터 나옵니다.

이 결과는 분석했던 시간 복잡도를 실제로 따른다는 실험적인 근거가 됩니다.

다른 종류의 큐

앞서 우선순위 큐를 FIFO 큐의 일반화로 바라보았습니다. 그렇다면 우선순위 큐가 FIFO 순서를 갖도록 만들 수도 있을 것입니다.

하지만 FIFO 큐를 우선순위 큐로 만들어서 최악의 경우 $\Theta(\lg n)$의 시간 복잡도를 갖게 만드는 대신, 별도의 데이터 구조를 만들어 $\Theta(1)$의 시간으로 줄일 수도 있습니다. 예를 들어, FIFO 순서로 노드를 더하고 없애는 링크드 리스트로 큐 인터페이스를 구현하는 것입니다. 이 부분은 직접 해보는 것으로 남기고 넘어가겠습니다.

한편, FIFO 순서의 반대로, 나중에 넣은 것을 먼저 꺼내는 LIFOlast-in first-out 큐도 상상해볼 수 있습니다. 손님이 줄을 선 상황에서는 어울리지 않을 수 있겠지만, 사실 스택과 똑같은 것이 됩니다. 따라서 LIFO 큐는 스택으로 만들면 모든 연산을 $\Theta(1)$의 시간이 들게 됩니다. 이 또한 직접 해보는 것으로 남기겠습니다.

힙소트

힙소트는 힙을 응용한 소팅 알고리즘입니다. 이 알고리즘이 배열을 소트하는 방법은 다음과 같습니다.

1. 주어진 배열을 트리로서 바라보고, 그것을 힙이라고 생각해봅시다. (힙이 아니더라도 힙으로 만들 수 있습니다.)

2. 루트 노드와 마지막 노드를 스왑합니다. 그러면 원래 루트 노드에 있었던 가장 큰 값은 마지막 노드에 위치합니다. 즉 가장 큰 값은 소트됐습니다.

3. 바뀐 루트 노드를 시프트 다운으로 내려 힙 오더를 유지합니다.

4. 마지막 노드를 다음 반복에서 제외시키고 이 과정을 반복합니다. 그러면 큰 값부터 마지막에 위치하게 되어 최종적으로 소트된 상태로 끝납니다.

이 과정을 표현한 수도코드는 다음과 같습니다. 배열이 힙 오더를 갖지 않을 수도 있기 때문에, 배열을 힙으로 만드는 heapify() 연산이 있다고 가정하고 나중에 만들어보겠습니다.

이 알고리즘은 배열의 크기가 $n$이라면 $\Theta(n \lg n)$의 시간 복잡도를 가집니다. 왜냐면 반복문에서 $O(\lg n)$의 시간이 드는 시프트 다운을 노드마다 반복하므로 총 $O(n \lg n)$의 시간이 들기 때문입니다. 그리고 이전 글에서 살펴본 것처럼, 비교 기반 소팅 알고리즘은 $\Omega(n \lg n)$의 시간 복잡도를 가집니다. 따라서 $\Theta(n \lg n)$의 시간이 들게 됩니다. 여기서 heapify() 연산은 곧 보겠지만 $\Theta(n)$의 시간이 걸리므로 결과가 달라지지 않습니다.

남은 숙제인 heapify() 연산을 만들어볼 차례입니다. 배열을 어떻게 힙으로 만들 수 있을까요?

간단히는 첫 번째부터 마지막 원소까지 시프트 업을 하는 것입니다. 하지만 더 좋은 방법이 있습니다. 반대 순서로 시프트 다운을 한다고 해봅시다. 그러면 리프 노드는 높이가 1인 트리로서 이미 힙이기 때문에 생략할 수 있고, 인터널 노드에 대해서만 시프트 다운을 하면 힙이 완성됩니다.

수도코드로 표현하면 다음과 같습니다.

이 알고리즘에 대해 최악의 경우의 시간 복잡도 $T(n)$으로 $O(n \lg n)$을 얻을 수 있기는 합니다. $\lfloor n/2 \rfloor$ 개의 인터널 노드에 대해 시프트 다운에 $O(\lg n)$의 시간이 들기 때문입니다. 하지만 좀더 자세한 분석으로 $\Theta(n)$라는 결과를 얻을 수 있습니다.

높이가 $h$인 노드는 트리에서 최대 $\lceil n/2^{h+1} \rceil$ 개가 있습니다. 여기서 $\lceil x \rceil$은 실링 함수ceiling function로 소수점을 올리기 위해 사용된 것입니다. 그리고 그런 노드에서 시프트 다운은 최악의 경우 $\Theta(\lg h)$의 시간이 든다고 했습니다. 이것은 상수 $c$에 대해 $ch$ 이하의 시간이 든다는 것과 같습니다. 따라서 모든 $h$에 대해 더하면 $T(n)$은 다음과 같습니다.

한편, heapify() 연산은 $\lfloor n/2 \rfloor$ 개의 인터널 노드마다 반복하기 때문에 $\Omega(n)$의 시간이 든다는 것은 바로 알 수 있습니다. 따라서 $T(n) = \Theta(n)$이 됩니다.

위에서 사용한 식 $\textrm{Eq.1}$은, $x \geq 1/2$에 대해 $\lceil x \rceil \leq 2x$ 라는 사실로부터 나옵니다. 여기서 $x=n/2^{h+1}$를 대입하면 바로 얻습니다. 식 $\textrm{Eq.2}$은 기하급수geometric series 식을 미분한 것으로부터 얻습니다. 즉 다음과 같이 유도할 수 있습니다.

여기에 $x=1/2$를 대입하면 원하는 결과를 얻습니다.

자바로 구현하기

앞서 heapify() 연산에서 마지막 인터널 노드를 구할 필요가 있었습니다. 이 노드는 마지막 노드 $last$로부터 $\lfloor (last-1)/2 \rfloor$로 구할 수 있습니다. 이것을 ArrayTree 클래스의 정적 메소드로 분리해봅시다.

class ArrayTree {
  // ...

  private static int getLastInternalNode(int last) {
    assert last >= 1;

    return (last-1)/2;
  }
}

그리고 루트 노드의 인덱스를 일반화한 것도 만듭니다.

  public static int getLastInternalNode(int last, int root) {
    assert root >= 0;

    return getLastInternalNode(last-root) + root;
  }

heapify() 연산은 수도코드를 그대로 옮겨서 Heapifier 클래스의 메소드로 만들어봅시다.

public class Heapifier<T> {
  // ...

  public void heapify(int root, int last) {
    int lastInternalNode = getLastInternalNode(last, root);

    for (int i = lastInternalNode; i >= root; --i) {
      this.siftDown(i, root, last);
    }
  }
}

소트는 이전 글에서 했던 것처럼 스트레터지strategy 패턴으로 만들 것입니다.

public interface ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp);
}

힙소트는 스트레터지로서 다음과 같이 만들 수 있습니다.

public class HeapStrategy<T> implements ArraySortStrategy<T> {
  public T[] sortArray(T[] arr, int begin, int end, Comparator<T> comp) {
    Heapifier<T> heapifier = new Heapifier<>(i -> arr[i], (i, value) -> arr[i] = value, comp);

    int root = begin;
    int last = end-1;
    heapifier.heapify(root, last);

    for (int i = last; i > begin; --i) {
      swap(arr, begin, i);
      heapifier.siftDown(begin, begin, i-1);
    }

    return arr;
  }
}

힙소트는 별도의 메모리 공간 없이 데이터를 직접 스왑하는 인플레이스in-place 알고리즘입니다.

소요 시간

이렇게 만든 힙소트의 소요 시간을 재봅시다. 배열이 이미 소트되었을 때와 반대 순서로 소트되었을 때를 각각 측정해보면 다음과 같습니다.

그래프가 보여주는 것처럼, 이론적인 시간 복잡도인 $\Theta(n \lg n)$을 따르는 근거가 됩니다.

마치며

처음에 힙을 이용해 풀 수 있는 문제로 멀티웨이 머지를 소개했습니다. 예를 들어, 세 개의 데이터셋 $D_1$, $D_2$, $D_3$이 소트된 채로 다음과 같이 주어지면, $D$처럼 하나의 소트된 데이터셋으로 리턴해야 하는 것입니다.

이 문제는 힙을 이용해서 어떻게 해결할 수 있을까요? 직접 풀어보는 것으로 남기겠습니다.

본문의 자바 코드는 생략된 부분을 포함해 깃허브GitHub에서 확인할 수 있습니다.

레퍼런스

• Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)

• Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)

• Algorithm 245: Treesort (Robert W. Floyd): (당시에는 다른 이름을 가졌던) 힙소트.