[edx] Binary Heap

Hyeon Soo·2022년 5월 19일
0

1. 개요

  • Binary Heap은 Binary tree이면서 complete한 특성을 가지고 있다.

  • Min heap은 tree에서 가장 작은 값이 root에 위치하고, 부모는 항상 자식보다 작아야 한다. 반대로, Max heap은 가장 큰 값이 root에 위치하고, 부모는 항상 자식보다 커야한다.

  • Heap은 Array로 표현할 수 있다. 0번 index는 비운 상태에서, root가 array의 1번 index에 위치하고, index번호를 n이라하면 left child는 2n, right child는 2n+1번째 index에 위치한다. 당연히, n/2번째 데이터는 부모이다.

  • Binary Heap은 특정한 특성을 가진 값 하나에 대한 접근을 가장 빠르게(O(1)) 하기 위한 자료구조이다. 그래서 priority queue를 구축하는 일에 쓰인다.

  • 값의 탐색은 O(n)이 걸리기에, 더 나은 자료구조를 사용하는 것이 낫다.

2. 동작

  • 탐색을 전혀 고려하지 않는 자료구조이므로, 최초의 heap build, add와 remove만을 신경쓰면 된다. 이때, Heap의 Min/Max값을 root로 보내는 특성보다는 항상 complete해야한다는 특성이 더 복잡하기 때문에 이를 먼저 맞춘 후 순서를 조정한다.

  • Add의 경우, 먼저 array의 맨 뒤에 데이터를 추가한다. 이 상태에서, 부모와 값을 비교하여 교체가 필요하면 교체한다. root에 이르기까지 비교와 교체를 진행하는 것으로 족하다.

  • Remove의 경우, root의 데이터를 최후미의 데이터와 바꾸어준다. 그 이후, 자식과 비교하여 필요시에 교체를 반복하는 것을 통해 형태와 순서를 유지한다.

  • 시간복잡도는 둘 모두 O(log n)이다.

  • Build의 경우, 단순하게 생각하면 Array의 첫 데이터부터 마지막 데이터까지 차례로 add하는 방법을 생각할 수 있다. 이 경우 O(nlog n)의 시간복잡도가 소요된다.

  • 다른 방법으로는, heap의 아랫부분부터 구축하는 방법이 있다. Array size의 반이 되는 index부터 자식과 비교하여 heap을 만들고, 그로부터 index를 하나씩 줄여나가며 heap의 순서를 맞추는 방법이다. 이 경우, O(n)이 소요된다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.

0개의 댓글