힙 트리란?
영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다.
힙은 항상 완전 이진 트리의 형태를 띄고, 부모의 값은 항상 자식(들)의 값보다 크거나(Max heap), 작아야(Min heap)하는 규칙이 있다.
따라서 루트 노드에는 항상 데이터들 중 가장 큰 값(혹 가장 작은 값)이 저장되어 있기 때문에, 최댓값(혹 최솟값)을 O(1)안에 찾을 수 있다.
단순히 최댓값(최솟값)을 O(1)안에 찾기 위해서라면 "항상 완전 이진 트리의 형태여야 한다"는 조건을 만족시킬 필요는 없다.
완전 이진 트리를 사용하는 이유는 삽입/삭제의 속도 때문이다.
물론 '힙 트리'는 정의상 완전 이진 트리를 사용한다.
달리 다른 구조를 사용한다 해도 전혀 얻을게 없는 최적의 구조이기 때문이다.
힙 정렬?
-
원소들을 전부 힙에 삽입한다.
-
힙의 루트에 있는 값은 남은 수들 중에서 최솟값(혹은 최댓값)을 가지므로 루트를 출력하고 힙에서 제거한다.
-
힙이 빌 때까지 2의 과정을 반복한다.
선택 정렬과 거의 같은 알고리즘으로.
단지 가장 큰 원소를 뒤로 보내는 데에 단순히 매번 쭉 돌면서 알아내느냐 힙(heap)을 사용하여 알아내느냐가 유일한 차이점이다.
힙 정렬은 추가적인 메모리를 전혀 필요로 하지 않는다는 점과, 최악의 경우에 의 성능을 내는 퀵정렬과 달리
항상 정렬의 성능을 발휘하는 장점이 있다.
하지만 실제 코드를 짜서 비교를 해 보면 퀵정렬이 힙정렬보다 일반적인 경우에 빠르게 동작한다.
그러나 아래 퀵정렬의 경우 피봇을 잡는 전략에 어느 정도의 휴리스틱이 들어가야 최악의 경우를 회피할 수 있으나
힙정렬은 휴리스틱이 필요없이 항상 일정한 성능을 보이는 장점이 있다.
즉 알고리즘에 꼼수를 쓰지 않고, 각종 하드웨어 가속도 전혀 고려하지 않고 알고리즘이 정의하는 최소한만 구현할 경우
힙정렬이 가장 안정적인 성능을 보인다.
https://youtu.be/6NB0GHY11Iw
힙 정렬(Max Heap) 파이썬 코드
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
print ("%d" %arr[i])출력 결과
c언어를 이용한 최대 힙(max heap) 삽입 연산
* 현재 요소의 개수가 heap_size인 힙 h에 item을 삽입한다. */
// 최대 힙(max heap) 삽입 함수
void insert_max_heap(HeapType *h, element item){
int i;
i = ++(h->heap_size); // 힙 크기를 하나 증가
/* 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정 */
// i가 루트 노트(index: 1)이 아니고, 삽입할 item의 값이 i의 부모 노드(index: i/2)보다 크면
while((i != 1) && (item.key > h->heap[i/2].key)){
// i번째 노드와 부모 노드를 교환환다.
h->heap[i] = h->heap[i/2];
// 한 레벨 위로 올라단다.
i /= 2;
}
h->heap[i] = item; // 새로운 노드를 삽입
}
//https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html
내림차순 정렬을 위한 최대 힙(max heap)의 구현
힙(heap)은 1차원 배열로 쉽게 구현될 수 있다.
정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다.
최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.
최대 힙(max heap)의 삽입
힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
힙 정렬(heap sort)의 시간복잡도
시간복잡도를 계산한다면
힙 트리의 전체 높이가 거의 log₂n(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는
시간이 log₂n만큼 소요된다.
요소의 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 걸린다.
정렬 알고리즘 시간 복잡도 비교
이제 시간복잡도
은 병합, 쉘만 남았다.
