Heap(힙)

 

Heap(힙)

---

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

💡 완전 이진 트리 : 이진 트리의 일종으로, 자식은 왼쪽부터 연결한다.
(왼쪽 자식이 없으면서 오른쪽 자식이 존재할 수 없다)

• 일종의 반정렬 상태를 유지한다.
  • 부모와 자식간에 정렬된 상태지만, 형제 노드간의 정렬은 이루어지지 않은 상태다.
• 중복된 값을 허용한다. (이진 탐색트리는 중복허용 X)

 

힙 종류

---

최대 힙(Max Heap)

• 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리

최소 힙(Min Heap)

• 부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리

 

힙 구현

---

• 일반적으로 배열을 사용한다.(연결 리스트로 구현할 수도 있긴 하다.)

• 구현의 편의성을 위해 0번 인덱스는 사용하지 않는다.
• 일정한 규칙을 유지한다.
  • 루트 노드의 인덱스 = 1
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

 

힙 삽입

---

마지막 노드의 위치를 알고 있기에, 새로운 노드가 추가될 위치를 알고 있다.

1. 새로운 노드를 마지막 노드 다음 위치에 삽입한다.
2. 새로운 노드와 부모 노드가 최대힙/최소힙 성질을 만족하지 않는다면 교체한다.
3. 2번 작업이 더이상 일어나지 않을 때까지 반복해서 올라간다.

• 최악의 경우에는 루트까지 교체작업이 이루어져야 한다.

→ O(logN)의 시간복잡도를 가진다.

 

힙 삭제

---

최대힙에서는 최대값, 최소힙에서는 최소값을 삭제한다.

1. 루트 노드를 삭제한다.
2. 빈 자리에 트리의 마지막 노드를 가져온다.
3. 자식 노드 중 더 큰 값(최소힙이라면 더 작은 값)과 교체한다.
4. 3번 작업이 더이상 일어나지 않을 때까지 반복해서 내려간다.

• 최악의 경우에는 리프노드까지 교체작업이 이루어져야 한다.

→ O(logN)의 시간복잡도를 가진다.

 

 

질문

---

Q. 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.

• ‘완전 이진 트리’이기 때문이다.
• 한 쪽으로 치우치지 않으면서 삽입,삭제 작업이 이루어진다.

•  

 

참고

---

[자료구조] 힙(heap)이란 - Heee's Development Blog