📝 힙의 정의
완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
🎯 힙의 특징
- 완전 이진 트리 자료구조의 일종이다.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아낼 수 있다.
- 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다.
- 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다.
- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 항상 크다.
- 힙 트리는 중복된 값을 허용한다.
✔이진 탐색 트리에서는 중복된 값을 허용하지 않는다. - 데이터가 n개일때 시간복잡도는 삽입시간 O(logN) / 삭제시간 O(logN)이다.
🧬힙(heap)의 종류
최대 힙(max heap)
- 루트 노드가 가장 큰 값을 가진다.
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
✔ key(부모 노드) >= key(자식 노드)
최소 힙(min heap)
- 루트 노드가 가장 작은 값을 가진다.
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
✔ key(부모 노드) <= key(자식 노드)
힙의 재정렬(Heapify)
Heapify는 힙을 고친다라는 의미로, 현재 삽입 혹은 삭제될 노드에 의해 전체 정렬 상태에 영향이 생길 경우 그 정렬을 다시 올바르게 진행하기 위한 절차를 의미한다.
삽입
- 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다.
- 완전 이진트리의 최대 높이는 O(logN)이고, 반복하는 최대 횟수도 O(logN)이 된다.
- 삽입 시에는 가장 마지막 배열 위치에 값을 우선 넣고 진행하므로 상단으로 힙을 재정렬해야 한다.
삭제(추출)
- 원소를 맨 위 넣어서 바닥까지 비교하면서 올린다.
- 완전 이진트리의 최대높이는 O(logN)이고, 반복하는 최대횟수도 O(logN)이된다.
- 현재 최우선 순위의 데이터를 추출해냈다면 배열의 가장 마지막에 있는 데이터를 최우선 순위 위치로 가져다 놓는다.
- 그 다음 아래 방향으로 재정렬(Heapify)를 진행하면 된다.
참고자료
도라에몽 암기빵