힙(heap)

이진트리

 

-> level간 숫자의 크기순서가 유지되는 자료구조

 

1. min heap : 상위 레벨(위쪽)에 더 작은 숫자 (더 작은 우선순위를 가진 데이터)가 있음

2. max heap : 상위 레벨(위쪽)에 더 큰 숫자 (더 큰 우선순위를 가진 데이터)가 있음

-> heap에서 pop을 하면, 무조건 오름차순(또는 내림차순)으로 데이터가 나온다!!

---

[데이터 추가]

1. heap의 제일 아래에 넣는다

2. 재정렬한다 (부모와 비교해서, 위치 바꾸기)

 

[데이터 삭제 (pop)]

1. heap의 루트노드를 pop한다

2. 루트자리에 heap의 제일 마지막에 있는 데이터를 넣는다

3. 재정렬한다 (자식과 비교해서, 위치바꾸기)