Heap

설명을 통일하기 위해 min Heap을 기준으로 한다.

Heap은 완전 이진트리의 일종으로써 최솟값(최댓값)을 빠르게 찾기 위해 고안된 자료구조이다.
출처

완전이진트리이기때문에 #Tree 에서 보다시피 배열로써 구현이 가능하다.

당연히 vector와 같은 동적할당을 사용해서 구현한다.

힙은 단 하나의 조건을 가진다. 자식은 부모보다 크거나 같다.
이 조건을 유지하며 삽입과 삭제를 하면 그것이 heap인 것이다.

이때 비교군이 특정 조건이나 열거형이 될 수도 있고, 정수가 될수도 있다.

삽입

1. 가장 뒤에 원소를 넣는다.

   배열로 구현되어있을 때 가장 마지막에 넣는다.

2. 넣은 인덱스에 부모와 비교한다.
   2-1. 부모가 크다면 위치를 바꾼다.
   2-2. 부모가 작다면 반복 실행을 멈춘다.
3. 루트노드까지 위 과정을 반복한다.

위와 같은 규칙을 따른다면 '자식은 부모보다 크거나 같다.' 는 대원칙을 지킬 수 있다.
이때 주목할 점을 반복을 루트노드까지 한다는 점이다.
트리에서 루트노드까지 반복한다는 것은 수행시간이 O(log N)이 된다는 뜻이다.

삭제

1. 루트노드를 제거한다.

   배열로 구현되어있을때 인덱스 1을 지운다.

2. 루트노드에 마지막 인덱스의 값을 넣고 마지막 인덱스를 지운다.
3. 넣은 인덱스에 자식과 비교한다.
   3-1. 자식 중 자신보다 큰 자식이 있다면 바꾼다.(자식이 모두 자신보다 크다면 자식 중 큰 수와 바꾼다.)
   3-2. 없다면 반복 실행을 멈춘다.
4. 리프노드까지 위 과정을 반복한다.

마찬가지로 '자식은 부모보다 크거나 같다.'라는 대원칙을 지킬 수 있다.
또 루트부터 리프까지 즉 O(log n)의 수행시간을 갖는다.

장단점

• 최대, 최소값을 상수시간에 찾을 수 있다.
• 삽입, 삭제 또한 로그시간에 수행가능하다.
  배열의 경우 삽입과 삭제가 상수시간에 가능하지만, 최대 최소값을 찾는데 선형시간이 소요된다.
• 특정 값을 찾는데 걸리는 시간은 기존 배열과 같다.

활용예시

• 우선순위 큐
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링