Heap(힙) 자료구조

Heap 

 

: 힙은 각 노드의 key값을 저장하고 다음의 특성들을 만족하는 이진트리이다. 

 

 

 

 

Heap's Property 

 

 

1. Heap-order(순서조건) 

: 루트를 제외한 모든 internal node에 대해  key(v) >= key(parent(v)) 만족 

→ sibling node끼리는 상관 없음! 이진'탐색'트리일 필요 없음 

 

 

 

2. Complete Binary Tree(구조조건) 

 

- 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드이다. 

→ 왼쪽 노드부터 삽입. 오른쪽 노드만 존재하는 노드가 있다면 해당 트리는 완전이진트리가 아님

 

 

 

Height of a Heap 

: n개의 key를 갖고 있는 힙은 height(O(logn)) 을 갖는다. 

 

 

※ 증명

 

heap 의 높이만큼의 수행횟수를 이용해 시간복잡도를 줄일 수 있지 않을까?

우선순위 큐를 구현하기 위해 힙을 사용한다. 
- 각각의 노드는 key, element 를 저장하고, 마지막 노드의 주소를 알 수 있게 연결되어 있음

 

 

 

 

 

Heap and Priority Queue

 

 

1. insertion into heap 

1) 삽입할 last node(z)를 추적한다

2) z에 k(key)를 저장한다. 

3) 힙 순서조건을 만족시킨다.(upheap)

 

Upheap O(log n) 

- key 삽입 후, heap의 순서조건이 위반될 수 있다. 

- 순서조건을 위반하는 첫 번재 노드(v)를 찾을 때까지 root로 올라가면서 key를 swap. 즉 바꿔준다. 

1) last node에 key 삽입 v

2) v노드와 v->par 비교 우선순위 위반x return; 

3) 우선순위 위반 시 v와 v->par의 key swap 

→ 재귀적으로 수행. 순서조건을 만족할 때까지 최악의 경우 O(log n)

 

 

 

2. removal from a heap

- 우선 순위 높은(min heap의 경우 root부터 삭제하게 됨)노드부터 삭제한다. 

1) root key와 last node key swap!!!

2) last node(v) 삭제한다. → last node의 포지션 업데이트 필요 

3) 힙 순서조건 만족을 위해 root 부터 순서조건 만족시키는 연산 (downheap) 수행

 

Downheap O(log n)

1) root와 last node key swap 이후 순서 조건 반드시 위반하게 됨

2) root 에서 부터 자식 노드 이동하며 swap

3) leaf 노드에 도달하거나, 순서조건을 만족하게 되면 return; 

 

 

 

마지막 last node는 어떻게 업데이트 할 수 있을까????

 

 

3. Updating the Last Node

 

- 삽입 연산 시 root에서 부터 내려가 찾기 O(log n)

1) 새로운 node 가 last node 지목하도록 

2) 해당 노드가 부모의 왼쪽 자식이 될 때까지 or 루트에 도착할 때까지 

3) 왼쪽 자식이 되면, 오른쪽 자식으로 이동 

3) leaf노드에 도달할 때까지 계속 왼쪽 자식으로 이동 

※ 삭제 연산 시 반대로 수행!!! 오→ 왼

 

 

 

 

Heap-Sort (힙 정렬)

 

 

O(n) - space

삽입, 삭제 연산 - O(log n) - time 

그 외 size, empty, min(root 리턴) - O(1) 

 

힙 정렬을 이용하면, n개의 요소들을 정렬하는 데 (n개의 삽입연산) O(n log n) - time

 

 

 

Implementation

 

1. Vector-based implamentation 

- n개의 key 와 n+1 크기의 vector 로 구현(index 0은 사용하지 않는다)

- 왼쪽 자식 2i, 오른쪽자식 2i+1

- in-place heap-sort (제자리 힙 정렬)

 

 

Merging Two Heaps  O(n)

 

힙정렬로도 빠른 수행이 가능하나, O(n) 으로 줄일 수 있는 방법이 있다. 
바로, 두 개의 node와 하나의 key가 주여졌을 때 두 힙을 하나의 힙으로 합치는 방법이다. 

 

1)  두 개의 힙과 key 하나를 받는다. 

2) 새로운 루트노드(key를 저장하는)와 두 개의 힙을 서브트리로 구성하는 새로운 힙을 생성한다. 

3) key에 따라 순서조건을 불만족할 수도 있기에, downheap 을 수행한다. 

 

 

 

Bottom-up Heap Construction O(n)

: merging 을 통한 효율적인 정렬 알고리즘 구현방법

하나의 루트가 있는 힙에 n개의 원소를 삽입하는 방식이 아니라, 

두 개의 힙을 합치고, 다운힙 과정을 반복하면서 힙을 생성한다. 
이렇게 생성 된 힙은 삽입 연산 시 업힙이 필요없어진다. (추가적인 노드 삽입이 있다면 예외가 발생하겠지만,,)

 

- i번째 단계에, 각각 2^i-1개의 키를 가지는 힙 쌍을 2^(i+1)-1개의 키를 가지는 하나의 힙으로 병합한다.

아직 bottom up heap construction 이해가 부족한 것 같다....