9-1. 힢

주요 용어

힢 : 부모노드와 자식노드사이의 대소관계가 정의되어 구성되는 완전 이진트리로 우선순위 큐와 같은 결과를 제공함

최대 힢 : 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨

최소 힢 : 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가지면 됨

 

 

01. 우선순위 큐

큐 : 먼저 들어간 데이터가 먼저 삭제되는 자료구조 먼저 줄을 선 사람이 먼저 서비스를 받는 구조

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

 

우선순위 큐의 작동 방식 : 

첫째, 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값)이 삭제된다.

둘째, 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다.

 

 

 

 

02. 힢

힢의 정의

- 피라미드 모양으로 쌓아 올린 더미

- 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조

- 부모-자식 노드사이에서 (부분적으로) 정렬된 포화 이진트리로 부모노드는 자식노드보다 우선순위가 높다.

 

힢의 추상자료형

힢의 추상 자료형

- 힢 객체의 정의 : 부분적으로 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높다.

- 연산 : 

   ① insert(element) ::= 힢에 데이터 삽입

   ② remove() ::= 힢 (루트)에서 데이터 삭제

   ③ peek() ::= 힢 (루트)에서 데이터 읽어오기

   ④ isEmpty() ::= 힢이 비었는지 확인

   ⑤ size() ::= 힢에 저장한 데이터 개수 확인

 

 

힢의 종류 :

최소 힢 :

루트가 전체 노드중에서 최소값인 힙

→ 트리의 모든 노드가 자식 노드보다 작은 값을 가짐

→ 트리의 레벨에 따라 데이터가 순서를 갖지는 않음

→ 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음

→ 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐

최대 힢 :

루트가 전체 노드중에서 최소값인

→ 트리의 모든 노드가 자식 노드보다 큰 값을 가짐

→ 트리의 레벨에 따라 데이터가 순서를 갖지는 않음

→ 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음

→ 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨

 

힢이 아닌 경우