[Coding Interview University] 힙 / 우선순위 큐 / 이진 힙 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🌝 힙(heap) 자료구조

: 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리 (complete binary tree) 를 기본으로 한 자료구조

: A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소 관계가 성립된다

: 완전 이진 트리

: 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 작아야 하는 자료구조

 

• 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 가짐

 

left : i * 2 + 1
right : i * 2 + 2
parent : (i - 1) / 2

 

• 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 가짐

 

🌝 힙(heap) 주요 메서드

peek() : 최대/최소값 리턴

size() : 힙 사이즈 리턴

isEmpty() : 힙 사이즈 0 체크

 

🌝 우선순위 큐 (Priority Queue) 자료구조

: 평범한 큐(queue)나 스택(stack)과 비슷한 축약 자료형

: 각 원소들은 우선순위를 갖고 있다

: 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다

• 스택(stack) - 원소들은 후입 선출 순으로 처리된다
• 큐(queue) - 원소들은 선입 선출 순으로 처리된다

 

🌝 이진 힙 (Binary Heap) 자료구조

: 완전 이진 트리 (각 레벨에 노드들이 꽉 차있는 이진 트리)

: 마지막 레벨 제외 (왼쪽부터 채워지며, 오른쪽에는 비워질 수 있음)

: 반 정렬상태를 유지

: 부모,자식 간에는 대소 관계가 있으나, 형제들 간에는 대소 관계가 정해지지 않음

→ 부분순서 트리 (PartialOrdered Tree)

: 중복된 값 허용 가능

 

🌝 이진 힙 (Binary Heap) 조건

: 루트 값이 항상, 제일 크거(최대 힙)나 제일 작거(최소 힙)나 해야 함

: 부모의 값이 자식 보다 항상 크다(최대 힙) 또는 항상 작다(최소 힙) 라는 조건을 만족 함

: 형제 간에는 값의 크고작음이 상관 없음

: 마지막 레벨을 제외하고는, 각 레벨의노드들이 모두 차 있음

: 맨 아래 레벨에서는, 왼쪽부터 꽉 채워져 있음

 

🌝 이진 힙 (Binary Heap) 종류

• 최대 힙 (Max-Heap) :루트 노드가 가장 높은 값을 갖고, 각 노드의 값이 자식 값 보다 큼
• 최소 힙 (Min-Heap) :루트 노드가 가장 낮은 값을 갖고, 각 노드의 값이 자식 값 보다 작음

 

🌝 이진 힙 (Binary Heap) 의 노드 위치 (인덱스)

: 왼쪽 자식노드 위치를 i라고 하면, 오른쪽 자식노드 위치는 i+1, 부모노드 위치는 i/2

 

🌝 이진 힙 (Binary Heap) 의 예시

: 힙정렬,다익스트라 알고리즘 (최단 경로),프림 알고리즘 (최소 신장 트리) 등

: 여러 자료 중에, 가장 큰 값이나 가장 작은 값을, 빠르게 찾기

 

🌝 이진 힙 (Binary Heap) 구현

• insert(e) : 요소 삽입
• remove() : 루트 또는 특정 요소 삭제
• peek() : 루트로부터 값 읽어오기
• poll() : 루트로부터 값 읽어오며 삭제
• isEmpty() : 힙이 비어있는지 확인
• size() : 힙에 저장된 자료의 개수 확인