#3 알고리즘 Advanced Data Structure : Binary Heaps

Heap은 기초적인 내용이지만 Binomial Heap을 다루기 위해 내용을 확실히 숙지해야 하므로 설명하고 넘어가도록 하겠습니다. 

Heap 이란?

  

  다음 조건을 만족하는 key값을 저장한 Binary Tree 입니다. 

  1. Heap-Order : 모든 노드는 자신의 부모노드보다 작거나 큰 값을 가진다. 

  2. Complete Binary Tree : 항상 왼쪽부터 꽉 채워져 있는 형태의 Binary Tree여야 한다. 

Heap과 Priority Queues(우선순위 큐)

  우리는 힙을 우선순위 큐, 다시말해 우선순위가 높은것을 먼저 나가게 하는데에 쓸 수 있습니다. Min heap은 key값을 오름차순 정렬 하는데 쓰일 수 있습니다. 

Heap에서의 Insert

  힙에서의 구조적 조건과 순서적 조건을 맞춰주면 끝납니다. 구조적 조건은 Complete Binary Tree이고 순서적 조건은 Heap Order입니다. 먼저 가장 마지막 삽입이 가능한 위치에 새로운 노드를 삽입하게 되면 구조적 조건은 만족하게 됩니다. 이후 Upheap을 통해 순서조건을 만족시키면 됩니다. 아래 그림은 가장 마지막 삽입 위치에 노드를 삽입함으로써 구조적 조건을 만족시키는 그림입니다. 구조적 조건을 만족시키는것은 매우 쉽습니다. 

  새로운 노드를 삽입한 후에 부모노드와의 크기비교를 통해 Upheap을 수행하게 됩니다. 자식노드는 부모노드보다 작다는 순서조건을 만족하면 upheap과정은 끝나게 됩니다. 

 Heap에서의 Delete

 

  Heap에서의 Delete란 root에 있는 가장 작은 값을 삭제하는 것입니다 삭제한 후 Upheap과 마찬가지로 구조조건과 순서조건을 만족시켜야 합니다. 구조조건을 만족시키기위해 가장 마지막 노드를 root로 가져옵니다. 이후 두 자식노드와 비교하여 더 작은것과 교환하며 더이상 작은 자식노드가 나오지 않을 때까지 Downheap을 합니다. 

Heap에 관련된 연산의 시간복잡도

  Insert는 힙을 만드는 과정입니다. 한번 insert할때마다 최대 heap의 높이만큼 upheap을 수행하게 됩니다. 힙의 높이는 log n이기 때문에 O(log n)입니다.

  Delete는 한번 수행시 마찬가지로 최대 heap의 높이만큼 Downheap을 수행하기 때문에 O(log n)입니다.

  힙을 생성하는것은 n개의 값에 대해서 Insert를 수행하는 것이므로 O(n log n)입니다. 힙을 삭제하는것, 다시말해 최소값을 계속 없애는 것은 값을 오름차순으로 정렬 하는것과 마찬가지입니다. 힙정렬은 n개의 값에 대해서 Delete를 수행하는 것이므로 O(n log n)입니다. 2*n*logn이므로 힙생성부터 정렬까지 총 수행시간은 O(n*logn)입니다.