[알고리즘] 최대 우선순위 큐, LowerBound

INSERT

max heap 에 새로운 것을 추가한다고 보면 heap이라는 것은 complete binary tree여야 합니다. 그리고 max-heap-property는 부모는 자식보다 크다라는 조건을 만족해야 합니다. 

 

heap은 complete binary tree를 가져야 하므로 노드를 하나 추가해야하는데

빨간 곳 말고는 없습니다. Insert하려는 값이 15라면 저 빨간 곳에 15를 저장할 수밖에 없습니다. 이렇게 하면 트리의 모양은 complete-binary-tree가 되지만 max-heap-property가 깨집니다. (부모가 자식보다 커야되는 것)

 

노드들간에 데이터를 exchange하고 새로 추가된 노드와 다른 노드에서는 문제가 없어보이며 크기를 비교하면 두 노드를 exchange하면 됩니다.

MAX-HEAP-INSERT(A, key)
{
	heap_size = heap_size+1;
    A[heap_size] = key;
    i = heap_size;
    while (i>1 and A[PARENT(i)] < A[i])
    {
    	exchange A[i] and A[PARENT(i)];
        i = PARENT(i);
    }
}

이 알고리즘의 시간복잡도는 O(h) - 높이 입니다. 자기보다 크면 트리에서 한레벨 올라가기 때문에 최악의 경우 루트에 도달하는 것이기에 높이가 되고 이 heap의 높이는 Complete binary tree의 높이는 log n이므로 O(log n)이 됩니다. 

 

EXTRACT_MAX()

max-heap은 최대값을 찾는 것에 관해서는 좋은 구조입니다. 

노드를 삭제할 때 complete binary tree를 유지하기 위해서 마지막 노드밖에 없습니다. 다른 노드를 삭제하면 complete binary tree가 아니게 됩니다. 데이터를 하나 삭제해야 하므로 줄여도 되는 노드는 마지막 노드입니다. 

 

그런데 6을 삭제하면 안되므로 마지막에 있는 데이터 6을 20과 바꿉니다. 그 다음 20을 삭제하는 것입니다. 이렇게 하면 트리의 모양은 complete binary tree이고 하나가 줄어들었습니다. 맨 마지막 값을 루트로 가져왔습니다.

 

현재 상황에서 노드 하나를 삭제했을 뿐, 나머지는 변함이 없으므로 heap property를 만족합니다. 이런 상황에서 트리 전체를 다시 heap으로 만들어주는 걸(heapify) 해줍니다. 정확히는 max-heapify입니다. 

 

HEAP-EXTRACT-MAX(A)
	if heap-size[A] < 1
    	then error "heap underflow"
    max <- A[1]
    A[1] <- A[HEAP-SIZE[a]]
    heap-size[A] <- heap-size[A] -1
    MAX-HEAPIFY(A, 1)
    return max

max heapify를 루트 노드에서 해주는 걸로 충분하고 시간복잡도는 O(log n)이 됩니다. 

 

Comparision Sort

n log n보다 낮아질 수 없습니다. 

 

Comparision sort

• 데이터의 크기 관계만을 이용하여 정렬하는 알고리즘
• 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용 가능
• 버블, 삽입, 합병, 퀵, 힙정렬 

Non-comparision sort

• 사전지식을 이용 - 적용에 제한
• Bucket Sort, Radix Sort

정렬 문제의 하한

어떤 comparision sort도 O(n log n)보다 낮을 순 없다. 증명하고자 하는 것

 

하한 (Lower Bound)

• 입력한 데이터를 한번씩 다 보기 위해서는 최소 O(n)의 시간복잡도가 필요
• 합병정렬과 힙정렬 알고리즘의 시간복잡도는 O(n log n )
• 어떤 comparision sort 알고리즘도 O(n log n)보다 나을 수 없다. 

Decision Tree

• 임의의 Comparision Sort가 있다고 가정합니다. insertion sort를 예로 들었을 때
• n개의 데이터가 입력으로 주어졌을 때 insertion sort가 정렬을 하기 위해서 값 비교해가는 전체 과정을 하나의 트리로 표현 가능 : Decision Tree

이 decision tree는 n!의 leaf node를 가집니다. 이는 a  b c에서 서로 다른 개수가 3!인 것과 같은 논리로 생각하면 됩니다.

 

Decision Tree의 Leaf 노드의 개수는 n!이며 최악의 경우 시간복잡도는 높이에 비례합니다. 트리의 높이는 height >= log n! = O(n log n)입니다.

 

full binary tree가 될 때 노드 개수는 많아지면서 높이는 최대한 낮게 됩니다. 이런 트리에서는 노드 개수가 n개면 O(log n)이 높이를 가지지만 노드의 개수가 n개가 아닌 리프 노드의 개수만 n!가 되어야 하므로 전체 노드의 개수는 n!보다 많고 트리의 높이는 log n!보다 낮을 수는 없습니다. 

 

이 log n!을 분석을 해보면 O(n log n)이 됩니다. 이는 stirling's theorem을 이용해서 정리를 해보면 나오는 것입니다. Comparision Sort를 decision으로 표현하면 n!을 가지며 이렇게 되려면 log n!보다 낮을 수는 없습니다. log n!을 정리를 해보면 O(n log n)이 되며 이보다 낮을 수는 없다는 사실을 증명할 수 있습니다.