자료구조 - 힙 (Heap)

1. 힙이란?

힙(Heap)이란 완전 이진트리 형태의 자료구조로 힙 조건을 만족한다. 일차원 배열로 구현할 수 있고 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다.

 

2. 최소 힙과 최대 힙

최소 힙과 최대 힙은 각각 다음 Heap Condition을 가지는 대표적인 유형의 힙이다. 부모노드의 키 값이 자식노드의 키 값보다 작은(큰) 관계가 유지되므로 트리 내에서 가장 작은(큰) 키 값을 가진 노드는 항상루트 노드가 된다.

1) 최소 힙 (Min Heap) : 부모노드의 키 값이 자식노드의 키 값보다 항상 작다.

2) 최대 힙 (Max Heap) : 부모노드의 키 값이 자식노드의 키 값보다 항상 크다.

 

3. 힙의 구현

1) 힙의 삽입 연산

① 트리의 가장 마지막 위치에 노드를 삽입한다.

② 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.

③ 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.

④ 조건에 만족하거나 추가된 노드가 루트에 도달할 때 까지 2~3을 반복한다.

◈ 완전 이진 트리의 리프 노드부터 루트 노드까지 연산을 함. 노드가 N개일 때 수행 시간은 O(logN)

 

2) 힙의 삭제 연산

① 힙의 삭제 연산은 항상 루트 노드를 삭제한다.

② 트리의 가장 마지막 노드를 루트 자리로 삽입한다.

③ 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.

④ 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.

⑤ 조건을 만족하거나 리프 노드에 도달할 때 까지 3~4를 반복한다.

◈ 완전 이진 트리의 루트 노드부터 리프 노드까지 연산을 함. 노드가 N개일 때 수행 시간은 O(logN)

 

4. 힙의 활용

1) 우선순위 큐

jina-developer.tistory.com/34

자료구조 - Priority Queue