도구란 우리가 생각하는 습관과 능력에 심오하고 교활한 영향을 끼치는 것이다.
The tools we use have a profound (and devious!) influence on our thinking habits, and, therefore, on our thinking abilities.
— 에츠허르 다익스트라Edsger Dijkstra (1975)
어느 가게에 손님이 몰렸다고 해봅시다. 그러면 손님들에게 대기 순번을 나눠줬다가, 여유가 생길 때마다 다음 손님을 받는 것으로 해결하게 됩니다.
이것이 프로그래밍 과제로 주어졌다고 상상한다면, 다음과 같은 데이터 구조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
부터 가집니다.
즉 레벨 는 부터 갖게 됩니다.
노드를 인덱스로 표현한다면, 부모와 자식 노드를 얻는 것은 인덱스를 계산하는 일과 같습니다.
먼저, 트리에서 각 레벨의 가장 왼쪽 노드를 바라봅시다. 그러면 이 노드는 다음 레벨의 가장 왼쪽 노드를 자식 노드로 가집니다. 다시 말해, 은 을 자식 노드로 갖습니다. 그리고 바로 오른쪽 노드인 또한 자식 노드가 됩니다. 따라서 부모 노드를 구하는 함수는 다음과 같이 인덱스를 인덱스로 보내는 함수가 됩니다.
다음과 같이 함수 로도 표현할 수 있습니다.
여기서 는 플로어 함수floor function로서, 소수점 이하를 버리기 위해 쓰인 것입니다.
사실 이 함수는 가장 왼쪽 노드 뿐만 아니라 나머지 노드에 대해서도 부모 노드를 구합니다.
따라서, 부모 노드를 구하는 getParent()
연산은 다음 수도코드와 같습니다.
getParent () // 노드 의 부모 노드를 리턴
이 연산을 거꾸로 하면 자식 노드를 구하는 연산이 됩니다. 먼저, 왼쪽 자식의 경우는 이렇게 만들 수 있습니다.
getLeftChild () // 노드 의 왼쪽 자식 노드를 리턴
그리고 여기서 하나 더 큰 것을 리턴하면 오른쪽 자식이 됩니다.
힙 프로퍼티 유지하기
이제 어떤 배열이 주어지면, 어떤 트리를 표현한 것으로 바라볼 수 있습니다. 하지만 힙 프로퍼티가 없을 수도 있으니, 꼭 힙을 표현한 것이라고는 할 수 없습니다.
따라서 트리가 힙 오더를 따르도록 만들 필요가 있습니다. 만약 어떤 노드가 힙 오더를 따르지 않는다면, 가능성은 둘 중 하나입니다.
-
그 부모 노드와 힙 오더를 따르지 않는다.
-
그 자식 노드와 힙 오더를 따르지 않는다.
따라서 각각의 경우를 해결해봅시다.
첫 번째 경우, 부모 노드를 따라 올라가며 필요할 때마다 자리를 바꿉니다. 이 연산에는 버블 업bubble up, 스윔swim 등의 여러 이름이 붙어있지만, 여기서는 시프트 업sift up이라고 부르겠습니다.
이 연산은 다음 수도코드처럼 표현할 수 있습니다.
siftUp () // 노드 가 힙 오더를 따르도록 위로 옮김
getParent()
만약 와 가 힙 오더를 따르는 경우이면
와 스왑
트리의 높이는 노드가 개일 때 이고, 시프트 업은 최악의 경우 높이만큼 반복하므로 의 시간이 든다는 것을 알 수 있습니다.
반면 두 번째 경우, 반대로 자식 노드를 따라 내려가며 자리를 바꿉니다. 이 때 더 큰 값을 가진 자식과 바꿔야 힙 오더를 유지할 수 있습니다. (이유는 직접 확인해보세요.)
이를 수행하는 시프트 다운sift down 연산은 다음과 같이 만들 수 있습니다.
siftDown () // 노드 가 힙 오더를 따르도록 아래로 옮김
두 자식 노드 중에 큰 것
만약 와 가 힙 오더를 따르는 경우이면
와 스왑
이때에도 최악의 경우 의 시간 복잡도를 가집니다.
이렇게 만든 연산은 트리가 힙 프로퍼티를 잃게 되는 경우, 다시 힙 프로퍼티를 갖게 만들기 위해 쓰일 수 있습니다. 그 구체적인 예는 우선순위 큐를 구현할 때 볼 것입니다.
자바로 구현하기
먼저 배열을 트리로 표현하기 위해, 배열에서 부모와 자식 노드를 구하는 연산을 만들어봅시다. 간단한 인덱스 연산에 불과하지만, 배열을 추상적인 트리로서 바라보기 위해 별도의 클래스로 만들어보겠습니다.
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()` 연산은 시프트 업으로 만들 수 있습니다.
즉 새 데이터를 마지막 리프 노드로 추가한 뒤에, 시프트 업으로 정리해 힙 오더를 따르도록 만듭니다.
add () // 값 를 힙에 추가
// : 힙을 표현하는 배열
// : 의 마지막 원소 인덱스
siftUp()
poll()
연산은 시프트 다운으로 만들 수 있습니다.
마지막 리프 노드를 루트 노드에 둔 뒤 시프트 다운으로 정리하면 힙 프로퍼티가 유지됩니다.
poll () // 힙에서 가장 높은 우선순위의 값을 리턴
// : 힙을 표현하는 배열
// : 의 마지막 원소 인덱스
와 스왑
삭제
siftDown() // 루트 노드 시프트 다운
리턴
add()
와 poll()
은 각각 시프트 업과 시프트 다운의 시간 복잡도를 따릅니다.
즉 값의 개수 에 대해, 둘 다 최악의 경우 의 시간이 듭니다.
자바로 구현하기
우선순위 큐가 가질 연산을 큐 인터페이스로 만들어봅시다.
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()
메소드의 소요 시간을 재봅시다.
이론적으로는 최악의 경우 의 시간이 든다고 분석했습니다.
다음은 개의 값을 우선순위 큐에 add()
로 추가한 경우와, 그렇게 추가하고 모두 poll()
로 꺼낸 경우를 측정한 것입니다.
그러면 다음과 같이 이론적으로 최악의 경우 의 시간 복잡도를 갖게됩니다.
여기서 이라는 사실은 스털링 근사Stirling’s approximation로부터 나옵니다.
이 결과는 분석했던 시간 복잡도를 실제로 따른다는 실험적인 근거가 됩니다.
다른 종류의 큐
앞서 우선순위 큐를 FIFO 큐의 일반화로 바라보았습니다. 그렇다면 우선순위 큐가 FIFO 순서를 갖도록 만들 수도 있을 것입니다.
하지만 FIFO 큐를 우선순위 큐로 만들어서 최악의 경우 의 시간 복잡도를 갖게 만드는 대신, 별도의 데이터 구조를 만들어 의 시간으로 줄일 수도 있습니다. 예를 들어, FIFO 순서로 노드를 더하고 없애는 링크드 리스트로 큐 인터페이스를 구현하는 것입니다. 이 부분은 직접 해보는 것으로 남기고 넘어가겠습니다.
한편, FIFO 순서의 반대로, 나중에 넣은 것을 먼저 꺼내는 LIFOlast-in first-out 큐도 상상해볼 수 있습니다. 손님이 줄을 선 상황에서는 어울리지 않을 수 있겠지만, 사실 스택과 똑같은 것이 됩니다. 따라서 LIFO 큐는 스택으로 만들면 모든 연산을 의 시간이 들게 됩니다. 이 또한 직접 해보는 것으로 남기겠습니다.
힙소트
힙소트는 힙을 응용한 소팅 알고리즘입니다. 이 알고리즘이 배열을 소트하는 방법은 다음과 같습니다.
-
주어진 배열을 트리로서 바라보고, 그것을 힙이라고 생각해봅시다. (힙이 아니더라도 힙으로 만들 수 있습니다.)
-
루트 노드와 마지막 노드를 스왑합니다. 그러면 원래 루트 노드에 있었던 가장 큰 값은 마지막 노드에 위치합니다. 즉 가장 큰 값은 소트됐습니다.
-
바뀐 루트 노드를 시프트 다운으로 내려 힙 오더를 유지합니다.
-
마지막 노드를 다음 반복에서 제외시키고 이 과정을 반복합니다. 그러면 큰 값부터 마지막에 위치하게 되어 최종적으로 소트된 상태로 끝납니다.
이 과정을 표현한 수도코드는 다음과 같습니다.
배열이 힙 오더를 갖지 않을 수도 있기 때문에, 배열을 힙으로 만드는 heapify()
연산이 있다고 가정하고 나중에 만들어보겠습니다.
heapsort () // 배열 을 소트
// : 의 마지막 원소 인덱스
heapify() // 배열 을 힙으로 재구성
다음을 부터 까지 마다 반복 // 루트 노드를 제외하고 역순으로 노드마다 반복
와 스왑
siftDown() // 노드 를 제외한 트리에서 시프트 다운
이 알고리즘은 배열의 크기가 이라면 의 시간 복잡도를 가집니다.
왜냐면 반복문에서 의 시간이 드는 시프트 다운을 노드마다 반복하므로 총 의 시간이 들기 때문입니다.
그리고 이전 글에서 살펴본 것처럼, 비교 기반 소팅 알고리즘은 의 시간 복잡도를 가집니다.
따라서 의 시간이 들게 됩니다.
여기서 heapify()
연산은 곧 보겠지만 의 시간이 걸리므로 결과가 달라지지 않습니다.
남은 숙제인 heapify()
연산을 만들어볼 차례입니다.
배열을 어떻게 힙으로 만들 수 있을까요?
간단히는 첫 번째부터 마지막 원소까지 시프트 업을 하는 것입니다. 하지만 더 좋은 방법이 있습니다. 반대 순서로 시프트 다운을 한다고 해봅시다. 그러면 리프 노드는 높이가 1인 트리로서 이미 힙이기 때문에 생략할 수 있고, 인터널 노드에 대해서만 시프트 다운을 하면 힙이 완성됩니다.
수도코드로 표현하면 다음과 같습니다.
heapify () // 배열 을 힙으로 재구성
// : 의 마지막 인터널 노드 인덱스
다음을 부터 까지 마다 반복 // 리프 노드를 제외하고 역순으로 노드마다 반복
siftDown()
이 알고리즘에 대해 최악의 경우의 시간 복잡도 으로 을 얻을 수 있기는 합니다. 개의 인터널 노드에 대해 시프트 다운에 의 시간이 들기 때문입니다. 하지만 좀더 자세한 분석으로 라는 결과를 얻을 수 있습니다.
높이가 인 노드는 트리에서 최대 개가 있습니다. 여기서 은 실링 함수ceiling function로 소수점을 올리기 위해 사용된 것입니다. 그리고 그런 노드에서 시프트 다운은 최악의 경우 의 시간이 든다고 했습니다. 이것은 상수 에 대해 이하의 시간이 든다는 것과 같습니다. 따라서 모든 에 대해 더하면 은 다음과 같습니다.
한편, heapify()
연산은 개의 인터널 노드마다 반복하기 때문에 의 시간이 든다는 것은 바로 알 수 있습니다.
따라서 이 됩니다.
위에서 사용한 식 은, 에 대해 라는 사실로부터 나옵니다. 여기서 를 대입하면 바로 얻습니다. 식 은 기하급수geometric series 식을 미분한 것으로부터 얻습니다. 즉 다음과 같이 유도할 수 있습니다.
여기에 를 대입하면 원하는 결과를 얻습니다.
자바로 구현하기
앞서 heapify()
연산에서 마지막 인터널 노드를 구할 필요가 있었습니다.
이 노드는 마지막 노드 로부터 로 구할 수 있습니다.
이것을 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 알고리즘입니다.
소요 시간
이렇게 만든 힙소트의 소요 시간을 재봅시다. 배열이 이미 소트되었을 때와 반대 순서로 소트되었을 때를 각각 측정해보면 다음과 같습니다.
그래프가 보여주는 것처럼, 이론적인 시간 복잡도인 을 따르는 근거가 됩니다.
마치며
처음에 힙을 이용해 풀 수 있는 문제로 멀티웨이 머지를 소개했습니다. 예를 들어, 세 개의 데이터셋 , , 이 소트된 채로 다음과 같이 주어지면, 처럼 하나의 소트된 데이터셋으로 리턴해야 하는 것입니다.
이 문제는 힙을 이용해서 어떻게 해결할 수 있을까요? 직접 풀어보는 것으로 남기겠습니다.
본문의 자바 코드는 생략된 부분을 포함해 깃허브GitHub에서 확인할 수 있습니다.
레퍼런스
-
Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
-
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
-
Algorithm 245: Treesort (Robert W. Floyd): (당시에는 다른 이름을 가졌던) 힙소트.