[자료구조] Heap & Priority Queue ADT

Heap이란?

Heap은 다음 두 규칙을 따르는 이진 트리의 일종이다.

1. 각 node가 가지고 있는 값은 각 node의 자식 node들이 가지고 있는 값보다 크거나 같아야 함(최대 힙의 경우)
2. 트리는 완전 이진 트리를 유지해야 하는데, 즉 가장 아래 레벨을 제외한 모든 레벨이 가능한 한 꽉 차 있어야 함.

최대, 최소 값을 빠르게 찾기 위한 자료구조이므로 BST랑 비교했을 때 비슷하다고 생각할 수도 있지만 Heap은 왼쪽 오른쪽 상관없이 상하 관계에 따라서만 크기 결정이 된다는 차이점이 있다. 

 

Heap을 이용한 우선순위 큐(priority queue) ADT

Heap 구조를 이용하는 우선순위 큐는 다음의 룰을 만족하면 된다.

1. 각 요소는 우선순위가 더 높은 상태로 유지가 되어야 한다.
   (부모 노드가 자식 노드보다 높은 우선순위를 갖추어야 한다는 뜻)
2. 트리는 완전 이진트리어야 한다.

Queue구조이기 때문에 root에서 나가고 완전 이진트리를 만족하는 leaf node의 위치로 들어오는 방식이다.

 

Element 추가하기

1. 완전 이진트리의 규칙에 맞게 삽입
2. 부모 노드와 비교해서 부모보다 크면 교환
3. 부모보다 작은 지점을 찾을 때까지 반복 || root에 도달할 때까지 반복

42를 새로 추가한 경우

 

Element 삭제하기

1. root의 node 제거
2. 가장 뒤의 요소를 root로 가져옴
3. 자식 노드와 비교해서 자식이 더 큰 경우 바꿈
4. 자식보다 큰 지점을 찾을 때까지 반복 || leaf에 도달할 때까지 반복

45를 뽑아내서 21이 root로 간 경우