Algorithm Study (힙)

이전내용 링크

 

완전탐색

정렬

문자열

배열,리스트

스택,큐

해시

 

실생활에서는 우선순위에 따라 일을 처리해야 하는 상황이 있다.

이런 경우에 사용되는 자료구조는 우선순위 큐가 있다.

우선순위 큐의 단순한 구현은 모든 배열에 원소를 넣고, 꺼낼때마다 전체 순회 하면서 우선순위에 따라 원소를 추출하는 방법이다.

해당 경우 원소 추가에 O(1), 원소 추출에는 O(N)이 걸리게 된다.

 

우선순위 큐는 이진 트리로 구현할 수 있고 힙 트리로도 구현 할 수있다.

원소의 삽입 삭제에 O(logN)이 걸리게 되며 대부분의 언어에서 힙을 표준라이브러리로 제공한다.

 

11. 힙(Heap)

완전 이진트리로 구성되어있으며(책에서 엄밀히 말하면 binary heap이라고 설명하고있으며, 이진트리가 아닌 구조로 이루어진 경우도 있다고 한다) 부모 노드의 원소가 자식노드의 원소보다 크거나 같도록 구성(Max Heap, 반대의 경우 Min Heap) 되어있다.

트리의 마지막 레벨을 제외하고 모든 원소가 채워져 있다.

트리의 마지막 레벨에 노드가 있을때는 왼쪽부터 오른쪽으로 채워진다.

트리의 높이(깊이)는 logN이다.

 

삽입 O(logN)

원소 삽입 시 모양 규칙에 따라 트리의 마지막 레벨에 원소가 추가된다.

부모노드와 비교하며 대소규칙(부모노드의 원소 >= 자식노드의 원소)에 따라 원소를 교환한다.

교환 작업에서 최대 트리 높이까지만 교환하면 되기 때문에 O(logN)으로 표현된다.

 

추출 O(logN)

힙의 첫 원소를 꺼낸다.

마지막 원소를 첫번째 원소의 자리에 위치시키고 자식노드와 비교하며 대소규칙에 따라 원소를 교환한다.

교환 작업에서 최대 트리 높이까지만 교환하면 되기 때문에 O(logN)으로 표현된다.