학습개요
힙은 완전이진트리형태이며 부모노드와 자신 노드간의 관계를 값이 대소관계를 적용하여 정의됩니다. 노드간의 관계에서 부모 노드가 자식노드보타 크면 최대힙이라고 하며, 부모 노드가 자식노드보다 작으면 최소힙 이라고 합니다.
힙에서 노드를 삭제하거나 삽입할 경우에는 완전이진 트리형태를 계속 갖춰야하고, 부모노드와 자식노드 사이의 대소관계도 계속 갖춰줘야 합니다. 즉, 노드간의 관계와 완전이진트리 정의를 만족시키며 노드의 삭제 연산과 삽입 연산을 구현해야 합니다.
학습목표
- 힙의 정의를 이해할 수 있다.
- 힙의 구성 방법을 이해하고 힙의 노드 삽입 연산과 삭제 연산을 이해할 수 있다.
- 최대힙과 최소힙을 이해할 수 있다.
연습문제
- 다음 설명으로 옳은 것은 무엇인가 ?
- 우선순위 스택 : 대기 리스트에서 항상 우선순위가 높은 것을 먼저 처리하는 구조
- 스택 : 먼저 들어간 데이터가 먼저 삭제되는 자료구조
- 최대 힙 : 루트가 최소값인 힙
- 배열을 이용한 힙의 구현은 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
–
- 지문은 무엇에 대한 설명인가 ?
트리의 모든 노드가 자식 노드보다 큰 값을 가짐
⇨ 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
⇨ 탐색 트리처럼 왼쪽, 오른쪽 노드 사이에 크기 제한도 없음
⇨ 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨
1. 선택 트리
2. 최소 힙
3. 최대 힙
4. 우선 순위 큐
정리하기
- 힙은 무엇인가를 쌓아놓은 더미이고 항상 가장 위에 있는 것을 우선 꺼내는 구조를 상징합니다. 그리고 힙은 우선순위 큐의 한 종류입니다.
- 힙은 완전 이진트리이며, 최소힙은 루트가 최소값이고 최대힙은 최대값입니다.
- 최대힙은 트리의 모든 노드가 자식 노드보다 큰 값을 갖는 것을 알 수 있습니다.
- 최소힙은 트리의 모든 노드가 자식 노드보다 작은 값을 갖는 것을 알 수 있습니다.
- 힙에서 노드를 삭제한 후에도 완전 이진트리의 모습을 유지해야 하며, 최대힙 혹은 최소힙의 조건을 만족해야 합니다.