힙 정렬

Heap

- 큰 키에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조.

- 한 노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리를 기본으로 함.

 

Heap 이 되기 위한 조건

1. 구조 조건 - 완전 이진 트리

2. 순서 조건 - Partial Order, 값의 순서가 직계 관계(부모-자식)에서만 성립.

 

이진 탐색 트리와의 비교

- 힙은 각 자식 < 부모. (최대 힙 트리라 가정.)

- 이진 탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식.

따라서, 힙은 우선순위 정렬에, 이진 탐색 트리는 탐색에 강점을 지닌 자료구조.

 

def heapify(unsorted, index, heap_size) :

	largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    
    if left_index < heap_size and unsorted[left_index] > unsorted[largest] :
    	largest = left_index
    if right_index < heap_size and unsorted[right_index] > unsorted[largest] :
    	largest = right_index
    
    if largest != index :
    	unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)

 heapify의 시간 복잡도는 최악의 경우 루트 노드에서 말단 노드까지 값을 비교해야 하므로 트리의 높이 (h=logn)에 의존적.

 

참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/