Heap(이강욱 선임님)

[자료구조 목차]

 

  

1. 우선순위 큐를 위한 Heap

1) 정의 

- 여러 개의 노드들 가운데서 최대값이나 최소값을 빠른 시간내에 찾아내도록 만들어진 완전 이진 트리 자료 구조

** 이진트리,  우선순위 큐

2) 특징

- 힙 순서 속성 만족, 대부분 이진 힙, O(log n)

 

2. Heap 의 종류 및 연산

1) Max Heap과 Min Heap

구분	Max Heap	Min Heap
개념도
개념	부모노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진 트리	부모노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전 이진 트리
힙 순서 속성	key(부모노드) ≥ key(자식노드)	key(부모노드) ≤ key(자식노드)

2) Heap의 연산

구분	설명
삽입 연산	1. 최고 깊이, 최우측에 새 노드 추가 2. 삽입 노드와 부모노드 비교 3. 삽입노드보다 부모노드가 작으면 연산 종료, 크면 위치 교환 4. 2번 단계 다시 진행
삭제 연산	1. 최고 깊이, 최우측에 있던 노드를 루트노드로 이동(힙속성 파괴) 2. 옮겨온 노드와 양쪽 자식 비교, 작은쪽 자식과 위치 교환 3. 옮겨온 노드가 더 이상 자식이 없거나 양쪽 자식보다 작은 값인 경우 연산 종료, 아닌 경우 2번 진행