학교에서 진행되는 자료구조 수업을 듣고 중요한 부분 위주로 정리하였습니다. 내용 상에 오류가 있다면 댓글로 피드백 부탁드립니다!
Priorty Queue
- insertion sort와 selection sort로 데이터를 정렬할 수 있습니다.
- list에 한번 insert하는데 O(n)의 시간이 걸리고 데이터의 개수가 n개이므로 O(n2)의 시간이 걸립니다.
- heap을 사용한다면 O(nlogn)의 시간만에 빠르게 정렬할 수 있어 list-based보다 heap-based priority queue가 효율적이라 배웁니다.
Heap이란?
두가지 조건을 만족시키는 자료구조
- heap-order property: 저장되는 key간의 관계가 일정하게 유지된다.
- complete binary tree: 마지막 level을 제외하고는 모두 채워져있으며 마지막 레벨의 노드는 왼쪽에서부터 채워진 트리
- full binary tree: 노드의 자식이 오직 0개 또는 2개인 트리
특징
- 마지막 level에서 가장 오른족에 있는 노드를 last node라 부른다.
- min heap: parent node의 key는 child node보다 작거나 같다
- max heap: parent node의 key는 child node보다 크거나 같다
- 트리의 높이 h = [O(nlogn)]
Operations
Insertion
- 새로운 last node를 추가
- heap-order property를 복원하기 위해 up-heap bubbling을 해주어야 한다.
up-heap bubbling: min heap일 경우, 추가된 last node의 entry의 key가 부모보다 작을 때까지 swap을 진행
Removal
- removeMin: root node와 last node를 swap하고 last node를 제거
- heap-order property를 복원하기 위해 down-heap bubbling을 해주어야 한다.
down-heap bubbling: min heap일 경우, 변경된 root node의 entry의 key가 부모보다 클 때까지 swap을 진행
Updating the last node
-
tree-based heap을 만들었을 경우 필요하다. array-based heap의 경우에는 last node를 인덱싱을 통해 업데이트가 가능하여 필요하지 않다.
-
removal이 발생하였을 때 새로운 last node의 위치를 찾는 연산이다.
-
로직
- 예전의 last 노드에서 시작한다.
- 예전의 last 노드를 포함하는 subtree가 right subtree가 될때까지 올라간다. 또는 루트 노드에 도달한다.
- 왼쪽 아래로 한번 이동하고 leaf node에 도달할 때까지 오른쪽 아래로 이동한다.
-
시간복잡도: O(log(2n))=O(logn)
Analysis of Heap-based PQ(Priority Queue)
-
insert: O(logn): updating the last node + adding the last node + up-heap bubbling
-
remove: O(logn): adding the last node + down-heap bubbling + updating the last node
Heap Sort
PQ를 Heap으로 구현할 경우
-
n번 데이터를 insert하고
-
n번 데이터를 remove합니다.
다음과 같이 시간복잡도를 구할 수 있습니다.
insert: $(n time insertion) O(logn) = O(nlogn)
remove: $(n time removal) O(logn) = O(nlogn)
따라서 총 시간 복잡도는 O(nlogn)입니다.
Array-based Heap
일반적인 binary tree를 array로 구현하였을 경우 skewed tree가 발생할 수 있어 O(2n)의 공간복잡도를 가질 수 있습니다. 따라서 자원을 굉장히 비효율적으로 사용하게게 될 수 있으나, complete binary tree의 경우에는 마지막 level을 제외하고는 모두 채워져서 공간을 효율적으로 사용할 수 있습니다. 또한 last node를 업데이트 할 필요없이 노드의 개수로 찾을 수 있어 O(1)의 시간이 걸린다는 것도 강점입니다. 추가적인 메모리 공간이 필요없는 in-place sort로 구현할 수 있습니다.
skewed tree: 한 쪽으로 노드가 치우쳐진 형태, leaf node를 제외한 모든 노드의 자식이 하나임, 선형적인 모양새
In-place heap sort
- 빈 heap에 element를 각각의 인덱스마다 채웁니다(한 element가 더해질 때마다 up-heap bubbling).
- root와 last node를 swap하고 down-heap bubbling을 합니다. 그 뒤에 last node로 사용되는 공간을 배제하고 그 전 인덱스의 노드가 새로운 last node가 되어 다시 swap을 하는 과정을 반복합니다.
Building a heap
- 하나의 새로운 heap을 만드는 경우: 계속 insert와 up-heap bubbling을 하면 됩니다.
successive insertions: O(nlogn) time
- 두개의 heap을 합치는 경우: 새로 만드는 것과 다른 방식으로 더 빠르게 heap을 만들 수 있습니다.
bottom-up construction: O(n) time
Bottom-up construction
- 힙 두개의 노드 개수만큼 채워지는 complete binary tree를 만든다.
- 가장 낮은 0번째 height부터 element로 채운다.
- 1번째 height부터는 element들은 down-heap bubbling이 이루어지도록 한다.
Analysis
- 한 노드는 최대 2번 방문되므로 노드의 총 방문 횟수 < 2n, 시간복잡도는 O(n)