힙(Heap)

우선순위 큐를 위해 만들어진 자료구조이다.

우선순위 큐는, 데이터들의 우선순위 차례대로 데이터가 나가는 자료구조를 말한다.

시뮬레이션, 작업 스케줄링, 수치해석 계산 등에 사용된다.

삽입, 삭제 모두 O(logN)이 걸린다.

1. 힙이란?

• 완전 이진 트리의 일종
• 최대, 최소값을 빠르게 찾도록 만들어진 자료구조
• 반정렬 상태(전체 정렬 상태가 아님!)
• 중복된 값을 허용한다
• 탐색에 적합하지 않다
• 특정 노드로 접근이 불가능하다

① 최대힙(C++)

② 최소힙(Java)

두 종류가 있다.

 

2. Heap vs BST(이진 탐색 트리)

BST

• 특정 노드 접근 가능
• 정렬된 상태 유지
• 중복 허용 X

Heap

• 특정 노드 접근 불가능
• 전체 정렬 X
• 중복 허용

 

부모 노드와 자식 노드 관계

왼쪽 자식 index = (부모 index) * 2

오른쪽 자식 index = (부모 index) * 2 + 1

부모 index = (자식 index) / 2

 

힙의 삽입

• 가장 마지막에 데이터를 삽입한다.
• 부모와 비교하면서 올라간다.

 

힙의 삭제

• 루트 노드를 삭제한다.
• 마지막 노드를 루트로 올린다.
• 자식과 비교하면서 내려간다.