[DataStructure&Algorithm] Heap, 힙

 

Heap

---

개요 - Heap이란?

Heap이란 Heap Tree 구조를 가지며, 여러 개의 값중에서, 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 이진트리 구조이다.

 

heap이라는 영단어 자체가 '어떤 것을 차곡차곡 쌓아올린 더미'라는 뜻이다. 이러한 이유로, 힙은 항상 완전 이진 트리 구조를 띄어야하며, 부모 노드의 값은 자식 노드의 값보다 기준에 따라 크거나, 작아야한다. 만약 큰 경우라면 root노드, 즉 최상단 부모 노드는 해당 배열에서의 최대 값을 가질 것이고, 작은 경우라면 반대로 최솟값을 가질 것이다. 이를 모두 Max Heap(최대 힙), Min Heap(최소 힙)이라고 한다.

 

이러한 구조적인 특징상, 최대 값이나 최소 값을 찾는데 매우 빠른 속도를 자랑한다.

---

특징

• 완전 이진 트리 구조를 지닌다.
• 데이터 삽입과 삭제 모든 O(logN)의 복잡도를 가진다.
  • 구조상, 한 층이 늘어날 수록 노드 수가 2배가 되기 때문이다.
• 비선형 자료구조이다.

---

데이터 삽입

1. 가장 마지막 노드쪽에 데이터를 삽입한다.
2. 부모 노드와 값을 비교한다.
3. 부모 노드와 값을 swap한다.
   1. 최대 힙인 경우, 자식 노드가 부모 노드보다 값이 큰 경우, 부모 노드와 값을 swap한다.
   2. 최소 힙인 경우, 자식 노드가 부모 노드보다 값이 작은 경우, 부모 노드와 값을 swap한다.
4.  힙의 규칙에 맞을 때까지 3의 과정을 반복한다.

힙 데이터 삽입 순서

데이터 삭제

힙 자료구조에서 데이터 삭제는 무조건 root 노드만 삭제한다.

1. 루트 노드를 제거한다.
2. 루트 자리에 마지막 인덱스에 저장된 값을 저장한다.(스왑)
3. 새로운 루트 노드와 자식 노드들을 비교한다.
4. 조건에 만족하면, 그대로 두고 그렇지 않다면, 스왑을 진행한다.
   1. 최대힙
      1. 부모보다 더 큰 자식이 없다면, 스왑하지 않고 종료.
      2. 하나 존재한다면, 해당 노드와 스왑
      3. 둘 존재한다면, 그 중 큰 노드와 부모노드 스왑.
   2. 최소힙
      1. 부모보다 더 큰 자식이 없다면, 스왑하지 않고 종료.
      2. 하나 존재한다면, 해당 노드와 스왑
      3. 둘 존재한다면, 그 중 큰 노드와 부모노드 스왑.
5. 조건을 만족할 때까지 반복한다.

 

 

---

응용

• 우선 순위 큐를 구현하는데 사용된다.
• 힙 정렬을 구현할 수 있다.