설명을 통일하기 위해 min Heap을 기준으로 한다.
Heap은 완전 이진트리의 일종으로써 최솟값(최댓값)을 빠르게 찾기 위해 고안된 자료구조이다.
출처
완전이진트리이기때문에 #Tree 에서 보다시피 배열로써 구현이 가능하다.
당연히 vector와 같은 동적할당을 사용해서 구현한다.
힙은 단 하나의 조건을 가진다. 자식은 부모보다 크거나 같다.
이 조건을 유지하며 삽입과 삭제를 하면 그것이 heap인 것이다.
이때 비교군이 특정 조건이나 열거형이 될 수도 있고, 정수가 될수도 있다.
- 가장 뒤에 원소를 넣는다.
배열로 구현되어있을 때 가장 마지막에 넣는다.
- 넣은 인덱스에 부모와 비교한다.
2-1. 부모가 크다면 위치를 바꾼다.
2-2. 부모가 작다면 반복 실행을 멈춘다.- 루트노드까지 위 과정을 반복한다.
위와 같은 규칙을 따른다면 '자식은 부모보다 크거나 같다.' 는 대원칙을 지킬 수 있다.
이때 주목할 점을 반복을 루트노드까지 한다는 점이다.
트리에서 루트노드까지 반복한다는 것은 수행시간이 O(log N)이 된다는 뜻이다.
- 루트노드를 제거한다.
배열로 구현되어있을때 인덱스 1을 지운다.
- 루트노드에 마지막 인덱스의 값을 넣고 마지막 인덱스를 지운다.
- 넣은 인덱스에 자식과 비교한다.
3-1. 자식 중 자신보다 큰 자식이 있다면 바꾼다.(자식이 모두 자신보다 크다면 자식 중 큰 수와 바꾼다.)
3-2. 없다면 반복 실행을 멈춘다.- 리프노드까지 위 과정을 반복한다.
마찬가지로 '자식은 부모보다 크거나 같다.'라는 대원칙을 지킬 수 있다.
또 루트부터 리프까지 즉 O(log n)의 수행시간을 갖는다.