자료구조 강의 9화 :: 힢(Heap), 우선순위 큐 구현 최강자

자료구조 9화를 듣고 배운내용

 

 

KEYWORDS

• 힢(Heap): 부모노드와 자식노드가 대소관계로 구성되는 완전 이진트리.
  우선순위 큐와 같은 결과
  
  
• 최대힢: 루트가 가장 큰 값을 갖고, 부모노드가 자식노드보다 큰 값을 가지면 된다.
  
  
• 최소힢: 루트가 가장 작은 값을 갖고, 부모노드가 자식노드보다 작은 값을 가지면 된다.

 

 

큐

먼저 들어간 데이터가 먼저 삭제되는 자료구조

먼저 줄을 선 사람이 먼저 서비스를 받는 구조

 

 

우선순위 큐

대기 리스트에서 우선순위가 높은 사람이 먼저 서비스를 받는 구조

삭제시

저장된 데이터 중에서 우선순위가 높은 데이터를 삭제한다.

나머지 데이터는 어떻게 저장되던 상관없다. 

 

 

Heap

우선순위 큐를 구현할 때 힢이 제일 효과가 좋다고 한다.

피라미드 모양으로 쌓은 더미

쌓아놓은 더미에서 항상 가장 위에 있는 것을 우선 꺼내는 구조

부모-자식 노드사이에서 정렬된 완전트리로,

부모노드는 자식노드보다 우선순위가 높다.

 

 

최소 힢

모든 노드가 자식 노드보다 작은 값을 가진다.

왼쪽에 큰게 오던, 오른쪽에 큰게 오던 상관없다. 

루트가 가장 작은 값을 갖는다.

 

 

최대 힢

최소 힢 잘 이해하고 반대로 생각하면 되겠다.

 

 

힢이 아닌 경우

• 완전 이진트리가 아닌경우
• 부모가 자식보다 작거나, 부모가 자식보다 크거나 일관성 있게 되어있어야 된다.

 

 

힢 구현

배열을 이용한 힢의 구현

힢은 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비 없다

• 연결 리스트보다 실행 속도 면에서 효율적
• 기억장소 측면에서도 장점을 가진다.

 

 

힢 노드 삭제

1. 프론트가 가르키는 것(루트 값)을 삭제한다.
2. 프론트가 삭제되면, 맨 밑에 노드를 프론트로 올린다.
3. 자식 노드와 비교하며 제자리 찾아준다.

 

 

힢 노드 삽입

1. 마지막에 노드 삽입 Cause 완전 이진트리 만들기 때문에
2. 부모 노드와 비교하면서 제자리 찾아주기

 

 

Pyamid by Louis Vanleer #unsplash