Heap - binary heap

Heap 이란

-> 이진 트리의 한 종류로 (이진 힙 - binary heap) 이라고도 함

 

조건

1. 루트(root) 노드가 언제나 최댓값 또는 최솟값을 가진다 (최대 힙 - max heap, 최소 힙 - min heap)

2. 완전 이진 트리여야 한다.

 

max heap -> 재귀적으로 정의 가능 : 어느 노드를 루트로 하는 서브트리도 모두 max heap 이다

 

이진 탐색 트리와의 비교

1. 원소들은 완전히 크기 순으로 정렬되어 있는가 ? X (이진 탐색 트리는 가능 )

2. 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가 ? X (이진 탐색 트리는 가능)

3. 부가의 제약 조건은 어떤 것인가 -> heap은 완전 이진트리여야한다는 조건을 가진다

 

Max Heap의 추상적 자료 구조

연산의 정의

- __init__() - 빈 최대 힙을 생성

- insert(item) - 새로운 원소를 삽입

- remove() - 최대 원소 (root node)를 반환 (동시에 이 노드를 삭제)

 

배열을 이용한 이진트리를 표현할 떄

노드 번호 m을 기준으로 

- 왼쪽 자식의 번호 : 2 * m

- 오른쪽 자식의 번호 : 2 * m + 1

- 부모 노드의 번호 : m // 2

 

완전 이진 트리이므로

- 노드의 추가/삭제는 마지막 노드에서만 가능하다