힙을 이용한 우선순위 큐 구현

1) 삽입연산 (push)

- 힙은 완전 이진 트리 형태이기 때문에 삽입연산을 할 때에는 배열의 길이면서 원소를 삽입해주는 인덱스를 표현해주는 len 변수를 선언해서 큐의 len에 원소를 삽입해주고 len의 길이를 1 늘린다.

- 그리고 나는 idx 라는 변수를 선언해서 새로운 원소가 삽입된 자리의 인덱스를 기억해서 부모와 우선순위를 비교 했다.

- 부모의 인덱스, 즉 idx / 2 와 비교 해서 idx가 더 작게 되면 자리를 계속해서 바꿔주고, 아니면 반복문을 빠져나간다. 여기서 주의 할 점은 삽입한 원소가 가장 우선순위가 높아 루트노드 까지 가게 되면 더이상 비교할 것이 없기 때문에 반복문을 멈춰줘야 하는데, while 문의 조건을 보면 idx > 1일때만 실행 되게 하여 idx 가 1이 되었을 때 (루트노드까지 올라갔을 때) 반복문을 빠져나오게 한다.

삭제연산(pop)과 비교했을 때 삽입연산의 코드는 비교적 간단하다.

2) 삭제연산 (pop)

- 삭제연산은 생각할 조건이 여러개가 있다. 먼저 삭제연산을 수행하게 되면 제일 우선순위가 높은 루트노드의 원소를 삭제하고, 가장 마지막에 있는 노드를 루트노드로 가져와서 2개의 자식중 우선순위가 높은 자식과 비교해서 자리를 찾아 주면 된다.

- idx 에는 삽입연산과 마찬가지로 1을 저장해서 삭제된 자리에 올라간 노드의 인덱스를 저장해서 비교하면서 계속 내려가는 역할을 해주는 변수 이다. 그리고 cIdx 라는 변수는 2개의 자식중 우선순위가 높은 노드의 인덱스를 저장해주는 변수이다.

- 힙은 완전 이진 트리 형태 이기 때문에 자식이 있는지 없는지 경우를 살펴 보아야 한다. 이부분은 세가지로 나뉜다. 여기서 주의해야 할 점은 오른쪽 자식만 있는 경우는 빼야하는데 그 이유는 완전 이진 트리이기 때문에 오른쪽 자식이 없는 경우는 없기 때문이다. 밑의 상황을 보면 쉽게 이해가 간다.

   2

    4                   8

    6        8           9     11

          ?     9

각각의 경우에 조건을 한번 보자.

① 자식이 없는경우 -> len은 힙의 마지막원소 다음을 가리키고 있으므로 len 의 길이가 idx * 2 즉 왼쪽 자식의 원소의 인덱스보다 같거나 작으면 idx의 자식이 없다 라는 뜻이다.

② 왼쪽 자식만 있는경우 -> 이 경우에는 코드에서 보듯이 여러가지 조건이 들어간다. 먼저 len의 길이가 1보다는 커야하고, idx * 2 (왼쪽자식) 이 len 보다 작아야한다. 같거나 작으면 안되는 이유는 len이 힙의 마지막원소 다음을 가리키고 있기 때문이다. 그리고 오른쪽 자식은 없다 라는 조건을 추가 해줘야 하는데 idx*2+1 을 하면 오른쪽자식의 인덱스를 가리키고 있기 때문에 이것이 len 이상이면 오른쪽자신이 없다라는 뜻이다.

③ 왼쪽 오른쪽 자식 둘다 존재하는 경우 -> 자식중의 높은 우선순위를 cIdx에 저장한다.

여기까지 진행하게 되면 cIdx 에 자식중 높은 우선순위의 인덱스가 저장되므로 이제 idx와 비교해서 자리를 바꿔주거나 반복문을 빠져나가면 된다.