일반적인 큐와 달리, 먼저 들어간 데이터가 아니라 우선순위가 높은 데이터가 먼저 나오는 자료구조
우선 순위를 적절이 조절함에 따라 일반적인 스택, 큐도 구현이 가능
힙을 통해 구현 가능
힙 : 부모 노드의 키 값이 항상 자식 노드의 키 값보다 큰 완전 이진 트리
배열, 연결리스트를 이용해 구현할 수도 있지만, 시간복잡도 면에서 힙을 통해 구현하는 방식이 효율적이다.
구현방식에 따른 시간 복잡도우선순위 큐 구현 방식 삽입시간 삭제시간
배열
$O(1)$
$O(N)$
연결리스트
$O(N)$ or $O(1)$
$O(1)$ or $O(N)$
힙
$O(logN)$
$O(logN)$
2. 힙의 개념
Complete Binary Tree
루트노드부터 왼쪽 → 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리
우선순위 큐를 위해 만들어진 자료구조
여러 개의 값들 중, 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
최댓값, 최솟값 탐색 시간 복잡도 : O(1)
삽입, 삭제 연산 시간 복잡도 : O(logN) - 최악의 경우에도 트리의 깊이 만큼만 비교하기 때문.
반 정렬상태 ( 느슨한 정렬 상태 )를 유지
항상 부모 노드의 키 값은 자식 노드의 키 값보다 크거나(작거나) 같다. → 루트 노드는 항상 우선순위가 가장 높은 노드다.
형제간의 우선 순위는 고려하지 않음.
중복된 값 허용.
3. 힙의 종류 - 최대 힙
key(부모 노드) ≥ key(자식 노드)
4. 힙의 종류 - 최소 힙
key(부모 노드) ≤ key(자식 노드)
5. 힙 구현 (최소 힙)
배열을 이용해 구현
특정 인덱스에 바로 접근 가능
연결리스트 - 검색, 이동 과정이 번거로움
부모, 자식 노드 간 인덱스의 연관
힙 ADT
ADT Heap
Characters:
i. array
Operations:
i. insert(x)
힙에 요소 x 추가
ii. int pop()
루트노드 제거, 값 반
iii. heapify()
(상향식) 부모 노드로 거슬러 올라가며 우선순위를 맞춤
배열이 힙 상태가 되도록 하는 과정
insert(x) : 노드 삽입하기
1. 삽입할 노드를 우선순위가 가장 낮다는 가정을 하고, 배열의 맨 끝 위치에 저장한다.
(왜 루트에 삽입하지 않는지도 생각)
2. 상향식 heapify()
pop() : 노드 삭제하기
1. 루트 노드를 삭제한다.
2. 가장 마지막 노드를 삭제된 루트 노드의 자리에 위치시킨다.
3. 루트노드와 자식 노드를 비교하며 힙이 완성될 때까지 교환을 반복한다.
