힙 정렬(Heaps sort)에 대해 알아보자!

힙(Heaps)이란 무엇인가?

 힙이란 트리(tree)처럼 생긴 데이터 구조이다. 부모가 자식보다 커서 내림차순 구조인 것을 max-heap, 부모가 자식보다 작아서 오름차순인 구조를 min-heap이라 한다. 데이터를 정렬하는 데 유용하게 쓰인다.

 다른 트리 데이터 구조와 달리 자식에 대한 포인터를 가지지 않고 데이터를 저장하는 데 배열을 활용한다. 이번 글에서는 바이너리 힙(binary heaps)만을 다루겠다.

---

힙 구조

min-heap 구조를 그림으로 나타내면 다음과 같다.

 

 

 위와 같은 min-heap은 뿌리 노드(root node)가 가장 낮은 값이 되고, max-heap은 뿌리 노드가 가장 높은 값이 된다.

 

---

바이너리 힙(Binary Heap)의 배열 인덱스 구조

 바이너리 힙에서 다음과 같은 배열 인덱스를 활용하여 배열로 구성된 힙의 요소를 나타낼 수 있다.

 

 

 위에 살펴본 인덱스를 활용하여 현재 노드의 인덱스를 기준으로 부모, 왼쪽 자식, 오른쪽 자식 요소를 불러내는 클래스를 작성해보겠다. 아래 클래스에서 peek 함수는 최고/최저값을 나타내는 데 쓰인다.

---

Heap 구현 코드

Prototype Ver.

Class Ver.

---

퍼컬레이션(Percolation): Bubbling Up and Down

 힙 구조에 값이 추가되거나 삭제될 때 힙의 꼭대기로 요소가 'bubble up'되거나 아래로 'bubble down'되어야 한다.

 다음 예는 min-heap과 max-heap에 요소를 추가했을 시 값이 정렬되는 과정을 나타내는 그림들이다.

 

Min-Heap

 

 

Max-Heap

 

---

힙 정렬 실행 코드

 위에 살펴본 min-heap 및 max-heap 정렬을 실행하는 코드를 살펴보자.

 

Min-Heap

Prototype Ver.

Class Ver.

 

Max-Heap

Prototype Ver.

Class Ver.