자료구조 Heap
우선 순위 큐(데이터들은 우선순위를 가지고 있고, 높은 우선순위가 먼저 나간다.)를 위하여 만들어진 자료구조
배열, 연결리스트, 힙을 이용하여 힙을 구현할 수 있다.
- 완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
- 힙은 일종의 반 정렬 상태(느슨한 정렬 상태)를 유지한다.
- 부모노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
자료구조 Heap의 종류
- 최대 힙(max heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 최소 힙(min heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
Heap 구현 (배열)
- 부모노드와 자식 노드의 관계
- 0번째 배열 인덱스는 사용하지 않는다.
- root 부모의 배열 인덱스는 1
- 왼쪽 자식의 배열 인덱스 = 부모 배열 인덱스 * 2
- 오른쪽 자식의 배열 인덱스 = 부모 배열 인덱스 * 2 + 1
- 부모 배열 인덱스 = (자식의 배열 인덱스) / 2
Heap 삽입 (배열)
- 새로운 노드는 부모노드와 조건을 비교후 삽입한다.
- 마지막 노드까지 비교후 삽입이 완료된다.
- 마지막 노드에 도달하면, 부모 노드와 비교후 부모보다 클 경우 교환을 반복한다.
Heap 삭제 (배열)
- 최대 힙에서 최대값은 루트 노드이므로 루트 노드를 삭제한다.
- 루트노드에는 힙의 마지막 노드(배열의 마지막 위치 노드)로 교체한다.
- 루트노드를 자식노드와 비교하여 큰 값과 교체 하며 재구성한다.
사례
네트워크 트래필 제어
운영체제 작업 스캐줄링
자료구조 처리순서 비교
스택
- 가장 최근에 들어온 데이터
큐
- 가장 먼저 들어온 데이터
우선선위 큐(Priority Queue)
- 우선순위가 높은 데이터