Heap이란?

Heap 정렬은 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식이다. 완전 이진 트리는 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리를 말한다.

다음 두 가지 힙의 종류가 있다.(부모-자식 관계)

• 최대 힙(Max heap): 각 노드의 값은 자식노드의 값보다 크거나 같은 완전 이진 트리.(부모 값 > 자식 값)
• 최소 힙(Min heap): 각 노드의 값은 자식 노드의 값보다 작거나 같은 완전 이진 트리.(부모 값 < 자식 값)

Heap정렬(Heap Sort) 알아보기

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.(내림차순을 기준으로 정렬)
2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
3. 삭제 방법(최댓값부터 삭제)을 통해 정렬을 진행한다.

---

Heap정렬의 특징

• 특징
  • 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
  • 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
  • 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

---

Heap정렬 구현

❝
다음의 데이터를 오름차순 정렬하세요.
7 6 5 8 3 5 9 1 6

1단계. 주어진 요소들의 배열을 최대힙/ 최소힙으로 만든다.(이번 예제는 최대힙)

주어진 데이터를 완전 이진 트리로 표현하면 다음과 같다. 정렬할 데이터를 완전 이진 트리에 삽입 되는 순서대로 인덱스를 붙여준다.

정렬을 하기 위해 완전이진 트리를 최대힙으로 만들어준다.

먼저 4번째 노드부터 본다. 부모의 값(7)이 자식값보다 작다. 15, 14 모두 7보다 크므로 자식값(15,14)을 비교하여 큰값(15)과 자리를 바꾼다.

3번째 노드를 볼차례다. 부모의 값(3)이 자식값보다 작다. 11, 13 모두 3보다 크므로 자식값(11,13)을 비교하여 큰값(13)과 자리를 바꾼다.

2번째 노드를 볼차례다. 부모의 값(5)이 자식값 15보다 작다. 따라서 5와 15의 자리를 바꿔준다.

4번째 노드가 바뀌었으니 다시 한 번 살펴보자. 4번째 노드 값(5)은 자식 노드(7,14)보다 작기 때문에 최대힙을 만족하지 않으므로 자식값중(7,14) 큰값(14)과 자리를 바꾼다.

이제 마지막으로 첫번째 노드를 확인한다. 그리고 마찬가지로 최대힙을 만족하기 위해 교환해주면 결과가 위의 오른쪽 트리와 같다.

2단계. 삭제 방법

힙정렬 1단계가 끝나고, 이를 배열과 완전 이진 트리로 나타내면 다음과 같다.

2-1단계) 맨 마지막 노드와 루트노드를 교환한다.

위와 같이 15와 14를 바꾼 뒤 15는 정렬이 완료된 것으로 생각한다.(노드가 “없다”고 생각)

2-2단계) 현재 루트노드에 대해 다운힙을 진행한다.
이는 최대힙을 만드는 과정과 같다.

루트노드(5)와 5의 자식인 14, 13을 비교한다. 가장 큰 자식 14와 바꾸어준다. 5가 자기자리를 찾아가도록 이와 같은 방법을 반복..

다운힙을 진행한 결과, 이제 다시 가장 큰 숫자인 14가 루트에 존재한다. 이를 가장 뒤 쪽의 원소와 서로 바꾼다.(2-1 단계)
현재 루트노드(1)에 대해 다운힙(2-2단계)을 진행한다.

이렇게 2단계 과정을 계속해서 반복해주면 정렬이 완료된다.

---

출처

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html https://zeddios.tistory.com/56