[자료구조] 힙

우선순위 큐

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

우선순위 큐의 작동방식

• 삭제 명령이 실행되면 저장된 데이터 중에서 가장 작은 값(가장 큰 값) 이 삭제 된다.
• 나머지 데이터들은 어떤 순서로 저장되든 문제가 되지 않는다.

힙 추상 자료형

힙의 정의

• 피라미드 모양으로 쌓아올린 더미
• 무엇인가 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조
• 부모- 자식 노드 사이에서 (부분적) 정렬된 완전 이진트리로 부모 노드는 자식 노드보다 우선 순위가 높음

힙 객체의 정의

• 부분적으로 정렬된 완전 이진 트리로 부모노드는 자식노드보다 우선순위가 높다
• 연산

연산 내용

insert(element)	힙에 데이터 삽입
delete()	힙(루트) 에서 데이터 삭제
peek()	힙(루트) 에서 데이터 읽어오기
isEmpty()	힙이 비어있는지 확인
size()	힙에 저장한 데이터 개수 확인

힙의 종류

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

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

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

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

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

힙이 아닌경우

• 완전 이진 트리가 아님
• 부모가 자식보다 작지 않음