1. 개요

힙을 설명하기 이전에, 정렬 알고리즘부터 설명하려 한다. 정렬 알고리즘이란 데이터가 들어오면, 오름차순이나 내림차순으로 정렬해주는 것이다.

정렬 알고리즘에는 다양한 종류가 있는데, 그 중 Insertion sort는 같은 공간 안에서 정렬을 하지만 최악의 경우, 시간이 많이 걸린다. 그에 반해 merge sort는 시간은 상대적으로 적게 걸리나, 메모리 공간을 많이 잡아 먹는다.

그래서 이 둘의 단점을 보완하여 나온것이 heap sort이다. 같은 공간에서 정렬하고, 시간을 덜 잡아먹는다. 또한 우선순위 큐(Priority Queue)로 쓰이기도 한다.

2. 정의

Max Tree: 각각의 노드값이 해당 노드의 후손(decendants)보다는 작은 트리
Max Heap: Complete 상태의 Max Tree
Min Tree: 각각의 노드값이 해당 노드의 후손(decendants)보다는 큰 트리
Min Heap: Complete 상태의 Min Tree

3. 원리

Min Heap은 Max Heap을 반대로 하면 되니, 여기서는 Max Heap에 대해서만 설명한다. 그리고 Complete한 상태이기 때문에 배열로 구현하는 것이 쉬우며 적절하다.

complete binary tree를 배열로 나타내면 위와 같은 이미지가 나온다. root의 index는 1, left child의 index는 (parents의 index X 2), right child의 index는 ((parents의 index X 2)+1)이다.

이 방식을 사용해서 부모 노드나 자식노드에 접근하여 조정하면 된다.

삽입시

max heap의 끝 부분에 새로운 노드를 하나 삽입한다.
max heap 상태가 만족될때까지 새로운 노드를 계속해서 조정한다.

삭제시

root에 있는 노드를 삭제하고, 맨 마지막 노드를 root 노드의 위치에 둔다.
root 노드에 있는 값이 children보다 작으면, max heap이 만족될 때까지 계속해서 조정한다.

삽입시에는 parents와 비교하면 되지만, 삭제시에는 left child와 right child를 비교해서 둘 중 더 큰 값과 교환한다.

4. 코드

maxheap, minheap 코드는 heap tree 코드를 상속해서 만들었다.

heap tree: https://github.com/21600055/DataStructures/blob/main/src/main/java/DataStructures/HeapTree.java

max heap: https://github.com/21600055/DataStructures/blob/main/src/main/java/DataStructures/Maxheap.java

min heap: https://github.com/21600055/DataStructures/blob/main/src/main/java/DataStructures/Minheap.java

heap sort: https://github.com/21600055/DataStructures/blob/main/src/main/java/DataStructures/Heapsort.java

5. 결과 이미지

a와 b 배열 둘 다 정렬된채로 나온다.

개인적으로 정리한 자료구조입니다. 수정되거나 건의할 사항이 있으면, 21600055@handong.edu로 메일 바랍니다.