Priority Queues, Heap

어떠한 구조인가?

data를 입력 받을 수 있으면서 request가 들어오면 제일 큰 값을 반환할 수 있는 구조

 

 

Implementation

1. Unsorted array or linked List

Insert : O(1)

removemax : O(n)

 

2. Sorted array or linked list

Insert : O(n)

removemax : O(1)

 

 

위 두 개의 구현 모두 O(n)이 걸리는 함수가 존재하여 효율적이지 못하다.

이를 해결하기 위하여 heap이 등장한다.

3. heap

Insert : O(logn)

removemax : O(logn)

 

 

Heap

Heap이란 ?

complete binary tree의 일종이다.

• Min-heap : 모든 value는 child value보다 작다.
• Max-heap : 모든 value는 child value보다 크다.

 

Partially ordered

모든 value들은 partially ordered이다 -> child간에는 order가 되어 있지 않고 부모-자식 간에만 ordered 되어 있다.

이는 Binary Search Tree와는 반대되는 성질이다(Totally ordered -> 모든 value들끼리 ordered 되어 있음)

 

 

Heap representation

보통 array-based로 구현을 한다.

Max Heap Example

floor(n/2) ~ n-1이 leaf node position이라는 것이 특징이다.

 

 

 

Building Heaps

H1, H2는 heap인 상황

위의 그림에서 left subtree와 right subtree가 heap이라면 R을 내려가면서 heap을 만들 수 있다.

R의 child들 중 큰 값과 R의 위치를 바꾼다.

그렇다면 여전히 R을 제외하고 나머지는 Heap을 만족하지만 R의 위치는 한 level 내려간 상태이다.

이를 R이 leaf가 될 때까지 반복한다면 주어진 트리는 heap이 될 것이다.

이를 siftdown operation이라고 하고, 원소의 개수가 n이라면 O(logn)이 걸린다.(tree의 깊이)

Siftdown operation

 

처음에 heap을 만들때는 어떻게 해야 효율적으로 만들 수 있을까?

만약 새로운 value들을 root에 집어넣어서 shiftdown을 반복한다면 코스트는 다음과 같다.

새로운 value를 root에 집어넣고 shiftdown 반복할때의 cost

반면 full array에서 시작하고 밑에서부터 shiftdown을 하는 것을 생각해보자.

많은 원소들이 제일 밑 level에 있기 때문에 cost가 거의 들지 않는다.(shiftdown을 할 때 원소가 속해있는 level의 height의 log값만큼 cost가 들기 때문)

식으로 써보면 다음과 같다.

full array로 시작하여 bottom부터 shiftdown operation을 시행했을 때의 cost

따라서 heap을 만들 때는 두번째 방법을 쓰면 효율적일 것이다.

 

 

Heap operation - RemoveMax, Insert

RemoveMax :

Heap이 유지되고 있다면 맨 위의 원소(Heap[n-1])을 반환하면 되니 이거 자체는 O(1)밖에 걸리지 않는다.

그러나 원소를 그냥 제거하면 Heap이 깨지게 된다. 따라서 가장 작은 원소와 자리를 바꾸고 제거를 해준다. 그 후 바꾼 원소에 대해서 shiftdown operation을 해야 하기 때문에 O(logn)이 걸리게 된다.

 

Insert :

추가할 원소를 Array의 가장 끝에 매단다. 그리고 그 원소와 parent의 value를 비교한다. Max-heap의 경우 추가한 원소가 parent의 value보다 크다면 자리를 바꾼다. 이를 parent의 value가 추가한 원소보다 클때까지 반복한다.

이 역시 O(logn)이 걸린다.