[자료구조] 힙(Heap)이란?
[자료구조] 힙(Heap)이란?
들어가기 전- 우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료 구조
- 데이터들이 우선순위를 가지고 있는 우선순위가 높은 데이터가 먼저 나간다
- 우선수위 큐의 이용 사례
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
- 수치 해석적인 계산
- 우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다
이 중에서 힙(Heap)으로 구현하는것이 가장 효율적이다.
자료구조 '힙(Heap)'이란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
- 힙 트리에서는 중복된 값을 허용한다.
- 이진 탐색 트리에서는 중복된 값을 허용하지 않는다.
힙(heap)의 종류
- 최대 힙 (max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- key(부모 노드) => key(자식 노드)
- 최소 힙 (min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- key(부모 노드) <= key(자식 노드)
힙(heap)의 구현
- 힙을 저장하는 표준적인 자료구조는 배열이다.
- 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
- 힙에서의 부모 노드와 자식 노드의 관계
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
- 부모의 인덱스 = (자식의 인덱스) /2
출처
댓글
댓글 쓰기