우선순위 큐 (priority queue), 힙 정렬 (heap sort)

우선순위 큐 (priority queue)

- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.

- 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다.

배열을 사용하는 방법

1. 정렬이 안 되어 있는 배열의 경우

삽입 시간 복잡도 \(O(1)\)

삭제 시간 복잡도 \(O(n)\)

2. 정렬이 되어 있는 배열의 경우

삽입 시간 복잡도 \(O(n)\)

삭제 시간 복잡도 \(O(1)\)

연결 리스트를 사용하는 방법

1. 정렬이 안된 리스트

- 삽입 시에 첫번째 노드로 삽입시키는 것이 유리하다. 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다.  삽입 시간 복잡도 \(O(1)\)

- 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다. 삭제 시간 복잡도 \(O(n)\)

2.  정렬된 리스트

- 우선순위가 높은 요소가 첫 번째 노드가 되도록 한다.

- 삽입 시에는 우선순위 값을 기준으로 삽입 위치를 찾아야 하므로 삽입 시간 복잡도 \(O(n)\)

- 삭제 시에는 첫 번째 노드를 삭제하면 되므로 삭제 시간 복잡도 \(O(1)\)

heap를 사용하는 방법

 heap는 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 

1. 일종의 반정렬 상태를 유지한다.

2. 효율은 \(O(log_2n)\)으로서 다른 방법보다 상당히 유리하다.

표현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결 리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결 리스트	O(n)	O(1)
heap	O(logn)	O(logn)

heap의 개념

- heap를 영어 사전에 찾아보면 "더미"라고 되어 있다. 컴퓨터 분야에서 heap는 완전 이진 트리 기반의 "더미"와 모습이 비슷한 특정 자료 구조를 의미한다.

- 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.

- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 

- 히프 트리에서는 중복된 값을 허용함에 유의하라. (이진 탐색 트리에서는 중복된 값을 허용하지 않았다.)

- 히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도이다. 히프의 목적은 삭제 연산이 수행될 때마다 가장 큰 값을 찾아내기만 하면 되는 것이므로 전체를 정렬할 필요는 없다.

heap의 구현

- 구현을 쉽게하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

삽입 연산

회사에서 신입 사원이 들어오면 일단 말단 위치에 앉힌 다음에, 신입 사원의 능력을 봐서 위로 승진시키는 것과 비슷하다.

1. 먼저 번호순으로 가장 마지막 위치에 이어서 새로운 요소 8이 삽입된다.

2. 부모 노드 4와 비교하여 삽입 노드 8이 더 크므로 교환한다.

3. 부모 노드 7과 비교하여 삽입 노드 8이 더 크므로 교환한다.

삭제 연산

회사에서 사장의 자리가 비게 되면 먼저 말단 사원을 사장 자리로 올린 다음에 강등시키는 것과 비슷하다.

1. 먼저 루트 노드가 삭제된다. 빈자리에는 히프의 마지막 노드를 가져온다.

2. 새로운 루트인 3과 자식 노드들을 비교해보면 자식 노드가 더 크기 때문에 교환이 일어난다. 자식 중에서 더 큰 값과 교환이 일어난다. 따라서 3과 8이 교환된다.

3. 아직도 3이 자식 노드들보다 더 작기 때문에 3과 자식 노드 5를 교환한다.

4. 3이 자식 노드인 2와 1보다 크기 때문에 더 이상의 교환은 필요 없다.

def heapify(unsorted, i, size) :
 
    largest = i
    left = 2*i
    right = 2*i + 1
 
    if left < size and unsorted[left] > unsorted[largest] :
        largest = left
 
    if right < size and unsorted[right] > unsorted[largest] :
        largest = right
 
    if largest != i :
        unsorted[largest], unsorted[i] = unsorted[i], unsorted[largest]
        heapify(unsorted, largest, size)

복잡도 분석

1. 삽입 연산

- 새로운 요소 히프 트리를 타고 올라가면서 부모 노드들과 교환을 하게 되는데, 최악의 경우 루트 노드까지 올라가야 하므로 거의 트리의 높이에 해당하는 비교 연산 및 이동 연산이 필요하다. 히프가 완전 이진 트리임을 생각하면 히프의 높이는 log_2n이 되고 따라서 삽입 연산의 시간 복잡도는 O(log_2n)이 된다.

2. 삭제 연산

- 마찬가지로 마지막 노드를 루트로 가져온 후에 자식 노드들과 비교하여 교환하는 부분이 가장 시간이 걸리는 부분인데, 이 역시 최악의 경우 가장 아래 레벨까지 내려가야 하므로 역시 트리의 높이만큼 시간이 걸린다. 따라서 삭제 연산의 시간 복잡도도 O(log_2n)이 된다.

---

Heap Sort (히프 정렬)

 최대 히프를 이용하면 정렬을 할 수 있다. n개의 요소는 O(nlog_2n) 시간 안에 정렬된다. 정렬 과정은 다음과 같다.

1. 정렬해야 할 n개의 요소들로 최대 히프를 초기화한다.

2. 한 번에 하나씩 요소를 히프에서 꺼내서 배열의 뒤부터 저장한다.

 히프 트리의 전체 높이가 거의 O(log_2n)이므로 (완전 이진 트리이므로) 하나의 요소를 히프에 삽입하거나 삭제할 때 히프를 재정비하는 시간이 O(log_2n)만큼 소요된다. 요소의 개수가 n개이므로 전체적인 O(nlog_2n)의 시간이 걸린다. 삽입 정렬 같은 간단한 정렬 알고리즘이 O(n^2) 걸리는 것에 비하면 좋은 편이다. 또한 히프 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때이다.

def heapify(unsorted, i, size) :
 
    largest = i
    left = 2*i
    right = 2*i + 1
 
    if left < size and unsorted[left] > unsorted[largest] :
        largest = left
 
    if right < size and unsorted[right] > unsorted[largest] :
        largest = right
 
    if largest != i :
        unsorted[largest], unsorted[i] = unsorted[i], unsorted[largest]
        heapify(unsorted, largest, size)
 
 
def heapSort(heap) :
 
    n = len(heap)
 
    # Build a maxheap.
    for i in range(n//2 - 1, -1, -1) :
        heapify(heap, i, n)
 
    # One by one extract elements.
    for i in range(n-1, 0, -1) :
        heap[i], heap[0] = heap[0], heap[i]
        heapify(heap, 0, i)
    

참고 :

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

https://www.geeksforgeeks.org/heap-sort/