힙 자료구조
binary heap
1. min heap
2. max heap
min heap : binary tree의 루트 노드가 이 트리 내의 다른 모든 값들보다 작아야 한다. sibling 끼리는 어떤 정해진 관계성이 존재 하지 않는다. 서브트리의 루트값이 최소값이면 된다는 조건말고 다른 조건은 필요하지 않다.
max heap : min heap 과 반대
heap에서의 operation 3가지
1. Top : 가장 작은값 (맥스 힙 값은 경우에는 가장 큰값) 을 찾아오는 동작. 루트 노드만 찾으면 되기에 constant time
2. pop : 루트에 있는 값을 제거하는것.
만약 3을 pop 하면, 7이나 12중 작은값을 promotion을 해야한다. 7을 promotion 하면 9와 31중 작은값을 promotion 해야한다. 이를 반복한다.
3. push : 어떤 임의의 값을 가지고 있는 바이너리 힙에 추가하는것.
leaf 노드에다가 아이템을 삽입해서 적당한 위치로 올라가게 하는 방법이 일반적이다. (binary heap 같은 경우에는 루트 노드에 삽입할때도 있다.)
바이너리 min힙에서 17을 삽입하겠다 하면 17을 그냥 아무 leaf 노드에 넣어준다. 그러면 min heap을 만족하지 않게되므로 17을 promotion 시켜줘야 한다. 17과 32를 비교해서 17이 작기때문에 32와 바꿔준다. promotion된 17과 31을 비교하고 17이 작기떄문에 promotion 시켜준다. 그리고 반복한다.
삽입된 노드는 위 노드로 promotion만 하지 아래로 내려오는 경우는 있지 않다. 삼투압 작용(percolation) 이라고 부른다.
perfect binary tree : 바이너리 트리의 높이가 h라고 했을때, 모든 leaf 노드가 depth h를 가지고 있는 경우.
모두다 자녀를 두개씩 가지고 있다.
왼쪽 서브트리와 오른쪽 서브트리가 모두 perfect 해야한다.
h가 0인 경우는 perfect 하다. h가 1인 경우는 왼쪽과 오른쪽 모두 perfect 하기에 전체도 perfect 하다.
높이가 h라고 하면 노드의 갯수는 항상 (2^h) - 1을 만족한다.
complete binary tree : perfect binary tree와 유사하지만, 어떤 노드 개수던지 정의가 된다.
perfect binary 처럼 노드들을 채워나간다. 노드를 채워나가는 순서가 BFS와 같다.
만약 N개의 노드가 있을때 높이는 logN에 해당한다.
push나 pop을 어떻게 complete binary tree의 형태를 유지한채로 수행할 수 있을까?
push는 그냥 형태에 맞게 넣어주고 percolation 해준다.
pop은 루트노드를 제거한뒤, 가장 마지막 leaf노드를 이동시킨다. 그리고 percolation down을 시켜서 원래 자기가 있어야 될 자리로 보내준다. 이런식으로 heap을 유지할 수 있는 이유는 BFS 오더로 하기 떄문이다.
힙을 실제로 구현할때는 array를 이용한다.
BFS 순서로 tree를 array에 넣으면 자신의 자식 노드를 자신의 노드 index*2 를 했을때 찾을 수 있다.
예컨데 4번 노드인 25는 자식 노드로 33과 55를 가지는데, 이것은 8번째 노드와 9번째 노드이다. 반대로 자식노드는 자신의 노드 index/2 또는 index/2 버림 했을때 찾을 수 있다.
포인터 없이 이렇게 쉽게 부모 자식간 관계를 알 수 있다. 편의를 위해서 array의 0번째 index는 비워둔다.
만약 push를 하게 되는경우, 원래 배열의 길이에 +1 index인 12 index에 추가를 한다. 그리고 min heap을 만족하는지 확인하기 위해서 12/2 index인 6 index의 값 23과 비교해서 26이 더 크므로 percolation을 하지 않아도 된다.
복잡도
Top : 상수 복잡도이다
pop : 빅 오 오브 lg(N). (N은 노드의 총 개수)
push : 평균적으로 상수 복잡도(?) 아래 공식에 따라.
특정한 수를 찾는 동작 : 빅 오 오브 N
가장 큰 아이템을 제거해줘 : 빅 오 오브 N
reference : http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2021_T1/courseware/d6f50ce290594d8d9a1fa7af097acb39/04854eb58b1b43838f9f770c36c42c02/?child=first