heap
•
우선순위 큐를 위해 만들어진 자료구조
◦
선입선출하는 일반 큐와 다르게, 우선순위가 높은 데이터가 먼저 나가는 시스템
•
완전 이진 트리의 일종
•
여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태이다.
•
중복된 값을 허용한다. - 이진트리는 중복값 허용 안됨
•
최대 힙
◦
부모 노드의 키 값이 자신 노드의 키 값보다 크거나 같은 완전 이진 트리
•
최소 힙
◦
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
•
예시
◦
시뮬레이션 시스템
◦
네트워크 트래픽 제어
◦
운영체제에서의 작업 스케줄링
◦
수치 해석적인 계산
•
장점
◦
최대값과 최소값을 찾아낼 때에도 시간복잡도 O(1) 로 가능하다.
◦
삽입과 삭제 연산 시에도 트리의 깊이만큼만 탐색하면 되기 때문에 시간 복잡도가 O(logN) 으로 매우 빠르다.
•
구현
◦
우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 그중에서도 힙으로 표현하는 것이 가장 효율적이다.
◦
힙을 저장하는 표준적인 자료구조는 배열
◦
구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.
◦
각 노드와 대응되는 배열의 인덱스틑 불변한다.
◦
“부모 노드는 항상 자식 노드보다 우선순위가 높다” 는 조건을 기억하며 완전이진트리 형태로 채워나간다.
최소힙, 최대힙
•
다시 한 번 기억하기
◦
“부모 노드는 항상 자식 노드보다 우선순위가 높다” 는 조건을 기억하며 완전이진트리 형태로 채워나간다.
◦
각 노드와 대응되는 배열의 인덱스는 불변한다.
◦
구현 쉽게 하기 위해서 첫 인덱스인 0은 사용하지 않는다.
◦
힙을 저장하는 표준적인 자료구조는 배열
•
성질
◦
왼쪽 자식 인덱스 = 부모 인덱스 * 2
◦
오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1
◦
부모 인덱스 = 자식 인덱스 / 2