✅ 비선형 자료구조 : i 번째 값을 탐색한 뒤의 i+1이 정해지지 않은 구조
힙(Heap)?
완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조. 일종의 반정렬 상태를 유지한다.
힙 트리 중복 값을 허용한다.
-
우선순위 큐 : 우선순위의 개념을 큐에 도입. 데이터들이 우선순위를 가지고 있어서 우선순위가 높은 데이터가 먼저 나간다.
-
반 정렬 상태 : 어려 값 중에서 최댓값과 최솟값을 빠르게 찾도록 만들어진 자료구조이다.
힙의 종류
최대 힙(Max Heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
최소 힙(Min Heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
힙의 구현
힙을 다루는 표준 자료구조는 배열이다. 높이 순서대로 조회하면 모든 노드를 배열에 낭비 없이 배치할 수 있다. 때문에 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
트리의 배열 구현의 경우 대부분 계산을 편하게 하기 위해 인덱스를 1부터 사용한다(0 인덱스는 비워둔다).
부모 노드와 자식 노드 찾기
- 부모의 인덱스 : (자식 인덱스) / 2
- 왼쪽 자식의 인덱스 : (부모 인덱스) * 2
- 오른쪽 자식의 인덱스 : (부모 인덱스) * 2 + 1
힙의 데이터 삽입
1. 가장 끝 자리에 노드를 삽입한다.
2. 그 노드와 부모 노드를 비교한다.
3. 규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다.
4. 규칙에 맞을 때까지 3번 과정을 반복한다.
최소 힙일 때
힙의 데이터 삭제
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
1. 루트 노드를 제거한다.
2. 루트 자리에 가장 마지막 노드를 삽입한다.
3. 올라간 노드와 그의 자식 노드들과 비교한다.
4. 조건에 맞으면 그대로 두고, 그렇지 않으면 자식과 교환한다.
-
최대 힙
- 부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.
- 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.
- 부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.
-
최소 힙
- 부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.
- 부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.
- 부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.
5. 조건을 만족할 때까지 4번 과정을 반복한다.
힙의 활용 사례
- 우선순위 큐 구현
- 힙 정렬
- 허프만 코드
우선순위 큐의 사용 사례
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
- 수치 해석적인 계산
출처 및 참고
프론트엔드 공부합니다. 블로그 이전: https://jinijana.tistory.com