힙

아래 영상이 잘 설명해 줍니다.

https://youtu.be/Zl07LUsR6P0 

 

1. 힙 개념

- 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만듦

- 명칭 : Heap tree

- 짧게 힙(Heap) 이라고 함

- 완전이진트리 (complete binary tree) 를 기본으로 한 자료구조

- 종류

• 최대 힙 (Max heap) : 항상  ' 부모노드의 키 값  >  자식노드의 키 값 '
• 최소 힙 (Min heap) : 항상  ' 부모노드의 키 값  <  자식노드의 키 값 '

- 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립함

- 형제 사이에는 대소관계가 정해지지 않음

 

- 그림 1

- 이진 트리의 모형

 

- 최소 힙

 

- 5 가 가장 작은 값이므로 제일 위에 있음

 

- 각 부모 노드들은 자식 노드들 보다 작은 값임

 

 

 

 

- 그림 2

최대 힙, 최소 힙 예시

 

- 그림 3

- 이거슨 힙이 아니다

 

- 그냥 이진 트리이다

 

- 부모 노드와 자식 노드간의 상관관계를 찾을 수 없음

 

- 부모노드 값이 자식노드들 보다 더 크거나 작아야 힙이 됨

 

 

---

2. 힙 실습

- 파이썬 으로 실습

- 문제

 

- 나의풀이

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- 틀림.. 실패!

 

그래도 태어나서 처음으로 몇개는 테스트 통과함..!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

- 다른 사람 풀이

- 먼저 받은 리스트를 최소 힙 구조로 정렬

- 반복문은 while 문을 사용

- scoville 을 최소 힙으로 정렬 했기 때문에 가장 작은 값이 맨 앞에 있음

- scoville 의 맨 앞에 값과 k 를 비교하면 됨

- 비교해서 작으면 섞음

- 아니면 while 문 끝

- 총 섞은 횟수 = answer

- 위 풀이 에서  if 문 의미 : 만약 scoville 에 값이 2개 이상이면 섞음

- else 의미 : scoville 값이 1개 이하이면 섞을 수 없어서, 섞을 수 없다는 뜻으로  -1 을 결과값으로 줌