힙(heap)의 용용 : 우선순위 큐(priority queue)

우선순위 큐 

- 최대 우선순위 큐

- 최소 우선순위 큐

 

최대 우선순위 큐

- INSERT(x) : 새로운 원소 x를 삽입

- EXTRACT_MAX() : 최대값을 삭제하고 반환

 

최소 우선순위 큐 

- EXTRACT_MAX 대신 EXTRACT_MIN을 지원하는 자료구조

 

INSERT

a) max heap의 형태

b) 아무 곳에 원소를 삽입하면 complete binary tree가 깨지기 때문에 삽입할 수 있는 위치가 정해져 있음, max heap property는 깨짐

c) heap property를 지키기 위해 부모노드와 현재 삽입된 노드를 교환함

 

INSERT 수도코드

- 새로운 원소를 삽입할 때 제일 마지막에 삽입해야 하므로 heap_size에 +1을 해준다.

- 배열의 마지막 원소로 추가

- 현재 삽입된 값이 부모보다 크면 교환해주고 원래 부모의 부모와 비교하기 위해 index값을 원래 부모의 값과 바꿔준다.

- 가장 높은 자리인 root가 될때까지 반복한다.

 

한번 비교할때마다 트리의 한 층씩 올라가는 것이므로 위 수도코드의 시간복잡도는 O(logn)이다.

 

EXTRACT_MAX()

 

a) heap의 형태일때 root가 가장 큰 값이므로 root의 값을 extract해준다.

b) root의 값이 빠질때 아무 노드나 삭제할 수 없다 -> complete binary tree구조가 망가짐

-> 마지막 노드만 삭제가 가능 -> 마지막 노드를 삭제된 root자리에 옮김

c) 자식과 비교하며 heap property를 맞춰감

 

EXTRACT_MAX()의 수도코드

- heap의 원소가 0개면 heap없다고 예외상황 출력

- max에는 현재 최대의 값을 넣어둔다.

- 배열에 처음값에 현재 마지막 값을 넣는다.

- 배열 사이즈를 하나 줄인다.

- max-heapify를 실행

- max를 리턴

 

위의 수도코드에서 max-heapify를 한번 실행할때와 나머지 명령문들을 실행할 때 상수를 포함해서 시간복잡도는 O(logn)이 된다.

 

** 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.