데이터 구조(2)-heap
힙( Heap )
- 힙은 그래프의 트리 구조 중 하나로 우선순위 큐를 구현할 때 사용된다
- 여러 개의 값 중에서 최솟값이나 최댓값을 빠르게 찾아내도록 만들어진 구조이다
- 힙트리에서는 중복을 허용한다
우선순위 큐: 우선순위의 개념을 큐에 더한 것이다
- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다
배열, 연결 리스트, 힙으로 구현 가능
힙 종류
최대 힙 (max heap)
- 부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
- 부모 노드 >= 자식 노드
최소 힙 (min heap)
- 부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
- 자식 노드 >= 부모 노드
힙 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다
- 배열의 0 인덱스는 사용 하지 않고 1부터 저장한다
- 노드 번호는 정보가 추가되거나 삭제되어도 변하지 않는다
- 힙에서 부모 노드와 자식 노드의 관계
▷ 왼쪽 자식의 인덱스 = 부모노드 인덱스 * 2
▷ 오른/쪽 자식의 인덱스 = (부모노드 인덱스 * 2) + 1
▷ 부모노드의 인덱스 = 자식노드 / 2
위 최소 힙을 배열로 저장하면
| 인덱스 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 값 | 1 | 3 | 6 | 4 | 6 | 7 |
최소 힙으로 확인하면 노드2, 노드4, 노드5의 인덱스를 보면 위 에 자식과 부모 노드의 관계를 확인 가능하다
힙 삽입
- 힙 에 새로운 요소가 들어오면 새노드를 힙의 마지막 노드 뒤에 삽입한다
- 새 노드를 두고나서 부모노드와 교환한다
힙 삭제
힙의 삭제에서는 최대 힙에서는 최대 힙 루트 노드(노드1), 최소 힙에서는 최소 힙 루트 노드가 삭제 된다
- 각각의 힙에서 루트 노드가 삭제된다
- 삭제된 노드에 힙의 마지막 노드 값을 가져온다
- 힙을 재구성 한다
이번 예시는 최대 힙
