스택이나 큐는 시간에 우선순위를 두어, 후입선출(Last-In-First-Out), 선입선출(First-In-First-Out)의 방법을 사용한다.
하지만, 예를 들어, 응급실에 실려오는 환자들을 생각해보자. 단순히 머리가 아픈 사람들보다는 손가락이 절단된 환자가 더 우선적으로 치료받아야 될 사람이다. 이러한 우선순위를 두는 자료구조를 우선순위 큐(Priority Queue)라고 한다.
우선순위를 매기는 기준은 당연히 여러가지가 있지만,
학습의 의미로써 우선순위 큐를 표현 할 때는 보통 숫자 혹은 알파벳으로 표현한다.
우선순위 큐(Priority Queue)를 배열로써 표현하거나, 연결 리스트로도 표현 할 수 있다.
둘 다 구현 효율은 O(N)이다.
또한, 이진탐색트리(Binary Search Tree, BST)로 구현할 때는 O(NlogN)이지만
이 것은 균형잡혀있는 이진탐색트리라는 전제조건이 있을 때이다.
하지만, 이제 자세히 알아 볼 우선순위 큐(Priority Queue)의 자료구조는
힙(Heap)이다.
힙은 완전이진트리로 표현되어야 하는데, 그래서 반드시 트리가 균형잡혀 있을 수 밖에 없다는 특징 때문에
시간효율을 O(NlogN)을 보장한다!!
힙의 정의
1) 항상 완전 이진트리의 모습을 지닌다.
2) A. 빈 트리거나,
B. 루트의 키가 왼쪽 자식, 오른쪽 자식의 키보다 크거나 같다.
왼쪽 자식과 오른쪽 자식 자시에는 어느 쪽 키가 크든지 상관없다.
단, 왼쪽 자식, 오른쪽 자식을 루트로 하는 하위트리는 힙이어야 한다.
다음은 맥스 힙(Max Heap)을 나타낸 것이다.
200은 왼쪽 자식인 100보다 크고, 오른쪽 자식인 80보다 크다.
200의 왼쪽 서브 트리 역시 힙의 형태를 띈다. 200의 오른쪽 서브 트리 역시 힙의 형태를 띈다.
- 대상 노드가 자식보다 크기만 하면 된다.
- 약한 정렬 형태를 가진 것을 알 수 있다.
- 완전 이진 트리 형태를 반드시 띄어야 하므로 배열로 표현하는 것이 유리하다.
우선순위의 기준?
맥스 힙(Max Heap), 민 힙(Min Heap)으로 나눌 수 있다.
루트노드가 자식노드들보다 큰 형태로 힙이 만들어지는 것을 맥스 힙(Max Heap)이라고 한다.
루트노드가 자식노드들보다 작은 형태로 힙이 만들어지는 것을 민 힙(Min Heap)이라고 한다.
힙의 특징?
힙의 가장 큰 특징은 완전이진트리로 표현해야 된다는 것이다. 그러므로 배열로써 자료구조를 표현한다.
위와 같은 힙이라는 트리를 배열로 표현하기에
1) 인덱스 K에 있는 모든 왼쪽 자식은 (2K+1), 오른쪽 자식은 (2K+2)에 있다.
2) 인덱스 K에 있는 모든 부모 노드는 (K-1) / 2 에 있다.
힙의 삭제?
힙의 삭제는 우선 순위가 가장 높은 루트 노드(Root Node)가 삭제되어야 한다.
배열로 구현하므로 24라는 노드를 할당해제 하는 식으로 삭제하는 것이 아니라 그 값을 지우고
힙의 마지막 값인 7로 대체한다.
7을 루트노드로 옮기면 자식노드보다 커야하는 힙의 성질이 깨지게 된다.
따라서 왼쪽 자식과
오른쪽 자식을 모두 비교해 가장 큰 것과 루트를 스와핑(Swap)해야한다.
7과 19, 7과 12를 비교 => 19가 가장 크므로 19와 7을 스왑
7과 17, 7과 10을 비교 => 17이 가장 크므로 17과 7을 스왑
7과 9를 비교 => 9가 더 크므로 9와 7을 스왑
이 처럼 힙 모습을 되찾으려면 루트로부터 시작해서 제자리 찾기까지 굴러 떨어져야 한다. => Down Heap
이 과정을 거치면 힙의 형태가 완성된다. => Heap Rebuilding
힙의 삭제 과정은 O(logN)이다. 배열의 마지막 레코드를 복사하는 것이 O(1)이다.
최악의 경우 리프노드까지 굴러 떨어져야 한다. 이 것은 logN이다. 그런데 비교때마다 왼쪽 오른쪽을 다 비교해야하므로
=> 2logN 이다.
힙이 이진탐색트리에 비해 유리한 이유는?
트리의 높이 때문이다.
이진탐색트리는 균형트리를 유지한다는 보장이 없지만, 힙은 반드시 균형트리를 이뤄야한다.
완전 이진트리이기 때문이다.
힙의 삽입?
힙의 삽입은 "새로 들어 온 직원을 말단의 자리에 앉히고 어디까지 올라가나 해봐라" 이렇게 말할 수 있다.
삽입 할 값을 마지막 노드에 삽입 한 후에 아래에서부터 부모와 비교하여 제 자리를 찾아간다.
22를 마지막에 삽입한다.
부모노드(10)과 비교한다. => 22가 더 크므로 스왑한다.
부모노드(19)와 비교한다. => 22가 더 크므로 스왑한다.
힙이 리빌딩됐다!
힙의 삽입 작업은 O(logN)이다.
최악의 경우 루트 노드까지 타고 올라가야 하므로 비교 횟수는 logN이다.
(삭제 노드는 자식 2개와 비교해야 되는데, 삽입 작업은 부모노드와 한 번만 비교하면 된다)
역시 이진탐색에 비한 장점은 균형트리를 보장하므로 logN을 보장한다는 것이다.
힙 정렬?
힙정렬은 힙의 형태를 이용해서 정렬을 하는 것이다.
최대 힙의 부모를 삭제하고 가져 온다. => 힙 리빌딩한다.
....(반복)
그러면 내림차순으로 값이 정렬된다.
반대로
최소 힙으로 하면 오름차순으로 값이 정렬된다.
힙 구성(Heap Building)?
힙 정렬을 위해서는 다음과 같은 두 가지 방법이 있다.
(1) 하향식 힙 구성(Top-Down)
반복적으로 힙에 삽입 작업을 가하는 것이다.
하향식 힙 구성의 시간 효율은
삽입 될 때마다 logN의 시간이 걸린다.
N개가 삽입 되므로 NlogN이 된다.
또한 정렬을 위한 힙의 삭제 단계에서 NlogN이 걸린다.
그러므로 O(NlogN) + O(NlogN) = O(NlogN) 이 된다.
(2) 상향식 힙 구성(Bottom-Up)
들어오는 키 값 순서대로 일단 트리를 구성한 후에 힙 구조가 되도록 재조정하는 방식이다.
그러한 후에 가장 아래서부터 오른쪽에서 왼쪽 순으로 힙의 구조인지 검사한다.
검사 할 때는 해당 노드와 해당 노드의 아래 쪽만 검사한다.
** 하향식과 상향식의 비교
- 둘 다 힙의 형태를 띄지만 그 트리가 완전히 똑같지는 않다.
- 완전 이진트리의 특성상 리프노드가 전체 노드의 반 또는 반이상을 차지하게 된다. (균형되게 유지되므로)
(1) 하향식 힙 구성 방법은
노드를 아래에 삽입 한 후에 위로 올라가면서 비교하여 리빌딩한다.
그러므로 가장 많은 노드를 차지하는 리프노드들이 logN의 시간을 타고 위로 올라가게 된다.
(2) 상향식 힙 구성 방법은
위에서 아래로 내리는 방법으로 리빌딩한다.
가장 많은 수를 차지하는 리프노드는 그 아래 노드가 없으므로 아예 비교조차 하지 않는다.
그 바로 위 레벨의 노드 역시 바로 아래와만 비교한다.
결국 logN의 장거리 여행을 하는 것은 루트노드와 같이 최상단에 있는 것만 한다.
하향식 힙 구성 방법이 O(NlogN)인데 반해
상향식 힙 구성 방법은 O(N)에 가까운 효율을 보인다.
