[자료구조] 힙(Heap)이란?

안녕하세요 시제품 개발 전문기업 디자인웨일입니다.

​

오늘은 힙(Heap)에 대해서 알아보겠습니다.

 

---

1.힙(Heap)이란?

​

​완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조입니다.

힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지합니다.

큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도

간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말합니다.

힙 트리에서는 중복된 값을 허용합니다.

(이진 탐색 트리에서는 중복된 값을 허용하지 않습니다.)

 

---

2. 힙(Heap)의 종류 ​

1 ) Max Heap(최대 힙)

Max Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 말합니다.

부모노드의 key >= 자식 노드의 key

​

2 ) Min Heap(최소 힙)

Min Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 말합니다.

부모노드의 key <= 자식 노드의 key

​

 

---

3. 힙(Heap)을 사용하는 이유

최솟값이나 최댓값을 찾을 때, 힙을 사용하면 O(logn)의 시간이

소용되기 때문에 배열을 사용할 때 보다 더 빠르게 최솟값과 최댓값을 구할 수 있습니다.

때문에 힙은 우선순위 큐나 최댓값, 최솟값을 빠르게 찾아야하는 알고리즘에서 사용 됩니다.

 

---

4. 힙/이진 탐색 트리 비교

힙	이진 탐색 트리
이진 트리 구조
최대 힙은 자식노드보다 부모노드가 크거나 같음 최소 힙은 자식노드보다 부모노드가 작거나 같음 but, 자식 노드끼리 크기로 위치를 정하지는 않음.	왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드의 순서로 크기 비교
최대/최소값 검색을 위한 구조	탐색을 위한 구조
중복값 허용	중복값 허용하지 않음

---

5.힙 정렬(Heap Sort)의 과정

정렬할 N개의 원소로 최대 힙 구성

최대 힙의 루트 노드(가장 큰 원소)와 마지막 원소 위치 교환

새 루트 노드에 대해 최대 힙 구성

원소 개수만큼 2와 3을 반복 수행합니다

 

---

6. 힙 만들기(build heap)

build heap은 힙이 아닌 배열을 힙으로 만드는 과정입니다.

이때 heapify를 N번 진행하게 되므로 시간 복잡도는 O(NlogN)입니다.

<build heap 과정>

가장 말단의 오른쪽에 있는 노드의 부모 노드부터 위에서 아래로 heapify를 진행합니다.

---

오늘은 힙(Heap)에 대해서 알아봤는데요.

​

시제품제작 상담과 제작의뢰는

디자인웨일로 문의 주시면 성심성의껏 빠르게 답해드립니다.

문의사항은 디자인웨일 홈페이지와 이메일로

보내주시길 바랍니다.

​

​

​

https://www.design-whale.com/contact

​

​

이메일:

info@design-whale.com

​

​

지금까지 시제품 개발전문기업 디자인웨일이었습니다.