Priority Queue

• Queue but items in it have priorities
• Simplest of Priority
  • no change of priority 우선순위가 바뀌지 않음
  • highest proirity comes out first 가장 높은 우선순위가 제일 먼저 나옴 (작은 값)
• Possible Array Implementations
  • Sorting → Delete는 빠르지만, insert의 경우 들어오면 하나씩 밀어줘야함
  • Unsorting → insert는 빠르지만, delete할 때 우선순위를 찾아야함

Binary Tree Implementation

Find Minimum in the Trees : go down left until you cannot 맨 왼쪽 아래가 첫번째 우선순위임

* AVL, 2-3, 2-3-4 or Red-Black Tree의 경우 맨 첫번째 우선순위가 아니라 전체 순위를 알 수 있음

ex) 높이가 아니라, 노드의 개수를 라벨로 가진다고 한다면, 왼쪽 라벨에 따라서 해당 노드가 몇 번째인지 알 수 있음

Heap Structure

Heap Definition

Complete Binary Tree

• All Levels Completely filled except for the last level
• Last level filled from left

parent has smaller key then children → no order for left and right children (large flexibility)

implications

• smallest at the Root 루트가 가장 작다
• key gets larger as you go down (in any direction) 어느 방향으로 가도 아래로 내려갈수록 커짐

Array Representation

우선순위 큐를 배열로

• Root is at index 1
• Left and Right Children of Node at index i are at 2i and 2i + 1
• 부모노드는 짝수라면 i/2 홀수라면 i-1/2이다 → Complete Binary Tree

Heap Insert (Up heap)

heap에 값 x가 추가됨

1. tree 모양을 맞추기 위해 x값을 그림과 같은 위치에 추가함 (크기 관계는 아직 고려하지 않음)
2. x와 c의 크기 관계를 확인해야함 (부모노드와 자식노드의 크기 관계 조건을 맞추어야 하기 때문)
   문제가 생길 가능성이 있는 것은 c-x 밖에 없음
   Case 1) x > c : 그대로 트리 유지
   Case 2) x  < c : x와 c를 변경
3. Case2의 경우, a와 x의 크기 관계에서 문제가 생길 가능성이 있음 → 반복하며 크기 관계에 따라 트리의 숫자를 변경

O(log N)의 시간으로 insert

 

Heap Delete

무조건 root에 있는 값이 Delete 되어야함 

heap delete

1. root에 있는 값을 삭제한 뒤, 가장 아래쪽에 있던 값을 root로 옮겨 모양을 맞춘다 (위 그림에서 x는 원래 맨 아래에 있던 값)
2. 크기 관계가 깨질 수 있는 곳은 x-c 와 x-b
   Case 1 ) b < c : b가 root
   Case 2) b > c : c가 root
3. x가 내려가게 된다면, 계속 아래의 크기 관계를 비교하여 2번과 같은 과정을 반복한다

O(log N)의 시간으로 delete