최대 힙과 최소 힙의 정의 / 힙의 삽입, 삭제 연산 방법 / 힙을 응용한 허프만 코드의 특징과 생성 방법

소개

"최대 힙과 최소 힙의 정의 / 힙의 삽입, 삭제 연산 방법 / 힙을 응용한 허프만 코드의 특징과 생성 방법"에 대한 내용입니다.

목차

1. 최대 힙과 최소 힙의 정의
2. 최대 힙, 최소 힙의 삽입과 삭제 연산 방법
3. 허프만 코드의 개념
4. 힙을 응용한 허프만 코드의 특징과 생성 방법
5. 참고문헌

본문내용

힙(heap)이란 피라미드 모양으로 차곡차곡 쌓아 올린 더미 모양을 말한다. 자료구조에서의 힙은 우선순위 큐를 구현하는 자료구조이며 빠르게 가장 크거나 작은 데이터를 찾을 수 있도록 만들어진 자료구조라고 정의할 수 있을 것이다. 이번 리포트에서는 최대 힙과 최소 힙의 개념, 연산 방법과 힙을 응용하는 방법인 허프만 코드에 대하여 설명하도록 하겠다.

1. 최대 힙과 최소 힙의 정의
힙은 최대 힙과 최소 힙으로 나뉘게 된다.

최대 힙(Maxheap)이란 부모 노드의 key 값이 자식의 key 값보다 크거나 같은 완전 이진 트리 형식이다. 즉, 루트 노드에 저장된 값이 트리 전체에서 가장 큰 값이 된다.

반대로 최소 힙(Minheap)은 부모 노드의 key 값이 자식의 key 값보다 작거나 같은 완전이진 트리 형식을 말한다. 즉, 루트 노드에 저장된 값이 트리 전체에서 가장 작은 값이 된다.

최대 힙과 최소 힙은 트리의 특성상 빠른 접근이 가능하며, 정렬된 순서를 유지하면서 값의 삽입, 삭제, 검색 등의 연산을 수행할 수 있다.

참고자료

· 다원 접속 (ktword.co.kr) 차재복 님의 개인연구실 정보통신기술용어해설
· 장원사이버평생교육원 자료구조 교안 참고