Heap 이란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 complete binary tree이다
최대 Heap
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 complete binary tree
key(부모노드) >= key(자식노드)
최소 Heap
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 complete binary tree
key(부모노드) <= key(자식노드)
Complete Binary Tree(완전 이진트리)
마지막 레벨을 제외한 나머지 레벨은 완전히 차 있어야 한다.
마지막 레벨에 있는 노드들은 왼쪽은 꽉 차있다가, 한 번 비어있기 시작하면 모두 비어있어야 한다.
즉, 배열로 표현했을 때 none 값이 실제 차 있는 값 중간에 있지 않다.
Order of Computation(log n)
height with n nodes tree
n개의 노드를 가지고 있는 Heap의 높이는 O(logn)
Heap은 complete binary tree
마지막 level h을 제외하고는 level i에 2^(i-1) 개의 노드 존재
O(logn)
Order of computation for height with n nodes tree
만약 100개의 노드를 가지고 있다면, log100 = 10, 높이는 10이다
Heap은 배열을 이용하여 구현한다.
complete binary tree 이므로, 각 노드에 번호를 붙일 수 있다. (1부터 붙인다)
이 번호를 배열의 인덱스라고 생각
부모노드 i와 자식 노드를 찾기가 쉽다.
왼쪽 자식의 인덱스 left = 2i
오른쪽 자식의 인덱스 right = 2i +1
부모의 인덱스 i = left/2, i = right/2
댓글