Heap (힙)

1) 힙

: 힙은 피라미드 모양으로 쌓아 올린 더미를 일컬음.

이는 제일 위에 있는 자료부터 선택해야 하는 구조를 상징함.

힙은 포화 이진 트리임. <그림 9-1>

: 최대힙 = 트리의 모든 노드가 자식노드보다 큰 값을 갖는 것을 일컬음.

최대힙에서는 루트가 최대값이 됨.

: 최소힙 = 트리의 모든 노드가 자식노드보다 큰 값을 갖는 것을 일컬음.

최소힙에서의 루트는 최소값과 같음.

<그림 9-1 힙>

2) 힙의 추상 자료형

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

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

: peek() = 힙(루트)의 데이터 읽어 오기

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

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

 

게시일: 2019. 3. 30. 16:43

원 주소: https://blog.naver.com/kwanho0096/221501276235

09. 힙