[자료구조] #18 Heap(1)

• 우선순위(Priority)

 

어떤 일을 먼저 처리할지 순서를 정하는 것이다.

 

• 우선순위 큐

 

우선순위의 개념을 큐에 적용한 자료구조이다.

우선순위를 가진 데이터를 저장하며 우선순위가 높은 데이터가 먼저 나가게 된다.

 

• 우선순위 큐의 ADT

 

데이터
item = <priority> (여기서는 key = value = priority라고 심플하게 하자.)

 

주요 연산
insert(item) : 우선순위 큐에 item을 추가

remove: 우선순위가 가장 높은 요소를 삭제하고 반환

find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환

 

우선순위 큐의 종류

최소 우선순위 큐 :  우선순위가 작을수록 우선순위가 높음

최대 우선순위 큐 : 우선순위가 클수록 우선순위가 높음 

 

• 우선 순위 큐의 구현 방법

 

1. 배열을 이용해서 구현

 

• 정렬되지 않은 배열
insert : 제일 마지막에 원소 삽입 O(1)

remove : 모든 원소를 살펴 우선순위가 높은 데이터 삭제 O(n)

 

• 정렬된 배열

 

insert : 정렬을 유지하기 위해 삽입 위치 탐색 O(n)

remove : 제일 마지막 원소 삭제 O(1)

 

2. 연결 리스트를 이용해서 구현

 

• 정렬되지 않은 리스트

insert : 첫번째 노드로 삽입O(1)

remove : 모든 원소를 살펴 제일 우선순위가 높은 데이터 삭제O(n)

 

• 정렬된 리스트

 

insert : 정렬을 유지하기 위해 삽입 위치 탐색O(n)

remove : 첫번째 원소 삭제O(1)

 

그렇다면 우선순위 큐의 insert와 remove를 동시에 더 효율적으로 할 수 있는 방법은 없을까?

 

그것이 바로 heap!

 

• Heap

 

자료구조에서 heap은 heap property를 만족하는 '완전 이진 트리'를 말한다.(binary heap)

 

heap이 되기 위한 조건은 두가지가 있다.

조건 1) Heap Property

조건 2) 완전이진트리

 

• Heap Property

 

Max Heap Property (최대 우선순위 큐)

부모 노드의 priority는 자식 노드의 priority 보다 크거나 같아야 한다.

 

Min Heap Property (최소 우선순위 큐)

부모 노드의 priority는 자식 노드의 priority 보다 작거나 같아야 한다.

 

Max/Min Heap

 

Max(Min) Heap은 최대(최소) 우선순위 큐를 위한 완전이진트리이다.

Max Heap에 대해 중점적으로 다뤄보도록 하자.

 

• 완전이진트리

 

높이가 h일때 레벨 1부터 h-1까지는 노드가 모두 채워진다.

마지막 레벨 h에서는 노드가 왼쪽에서 오른쪽으로 순서대로 채워진다.

 

Heap을 완전 이진 트리로 유지했을때 장점

Heap의 높이를 최소로 만들 수 있다.

트리 내 노드가 순서대로 차기 때문에 배열로 구현할 때 중간에 빈 공간이 없다.

 

일반적으로 중간에 비어 있는 요소가 없기 때문에 배열로 구현한다.

구현을 간단하기 하기 위해서 root의 index를 1로 할당한다.

 

• Insert

 

item x = <priority>를 heap에 insert

 

Step 1) Heap의 제일 마지막에 입력 항목을 추가한다.

(Heap의 제일 마지막 = open space의 가장 왼쪽)

 

Step 2)  부모와 추가된 항목의 우선순위를 비교한다.

부모와 자식이 올바른 순서로 존재하면 stop한다.

올바른 순서가 아닐시 부모와 자식 노드를 swap하고 Step 2를 반복한다.

 

멈출 때까지 상위 레벨로 올라가는 형상이기 때문에 Up-heap이라고 한다.

def insert(priority):
    size ← size + 1          # 힙 크기 증가
    i ← size                 # 새 위치
    nodes[i] ← priority      # 우선순위 삽입
    while i != 1 and nodes[i] > nodes[PARENT(i)]:
        swap nodes[i] and nodes[PARENT(i)]  # 부모와 교환
        i ← PARENT(i)       # 부모 노드로 이동

 

• Remove

 

우선순위가 가장 높은 원소 삭제 = 루트 노드 삭제

 

Step 1) 마지막 레벨의 가장 오른쪽에 있는 노드를 루트로 대체한다.

 

Step 2) 루트를 시작으로 양쪽 자식과 우선순위를 비교한다.

부모와 자식들이 올바른 순서로 존재하면 stop한다.

올바른 순서가 아닐시 부모와 자식 노드를 swap하고 Step 2를 반복한다.

 

멈출 때까지 하위 레벨로 내려가는 형상이기 때문에 Down-heap이라고 한다.

def remove():
    highest ← nodes[1]       # 루트 노드(최고 우선순위) 저장
    nodes[1] ← nodes[size]   # 마지막 노드를 루트 위치로 이동
    size ← size - 1          # 힙 크기 감소
    down-heap(1)             # 루트에서 down-heap 연산 수행하여 힙 속성 복구
    return highest           # 저장된 루트 노드를 반환

def down-heap(i):
    left ← LEFT(i)           # 왼쪽 자식 노드 인덱스
    right ← RIGHT(i)         # 오른쪽 자식 노드 인덱스
    largest ← i              # 현재 노드를 가장 큰 노드로 초기화
    if left <= size and nodes[left] > nodes[largest]:
        largest ← left       # 왼쪽 자식이 현재 노드보다 크면 largest 갱신
    if right <= size and nodes[right] > nodes[largest]:
        largest ← right      # 오른쪽 자식이 현재 largest보다 크면 largest 갱신
    if largest != i:
        swap nodes[i] and nodes[largest]  # 현재 노드와 가장 큰 자식 노드 교환
        down-heap(largest)                # 가장 큰 자식 노드에서 재귀적으로 down-heap 호출

 

• Heap의 시간복잡도

 

n을 heap에 저장되어 있는 아이템의 수라고 하자.

 

Insert : O(h) = O(log n)

Up-heap은 최대 높이 h번 만큼 위로 올라가면서 연산을 수행한다.

Heap은 완전 이진 트리로 O(log n)의 높이를 가진다.

 

remove : O(h) = O(log n)

Down-heap은 최대 높이 h번 만큼 아래로 내려가면서 연산을 수행한다.

 

즉, 배열이나 연결리스트(O(1), O(n)) 보다 균형이 잡혀있기 때문에 효율적이라고 할수 있다.