[자료구조] 우선순위 큐의 완성

[자료구조] 우선순위 큐의 완성

힙을 사용하여 삽입, 삭제 등 우선순위 큐와 근접하게 완성해 보았다.

하지만 지금까지 구현한 우선순위 큐에는 한가지 문제점이 있는데

데이터와 함께 우선순위에 대한 정보를 사용자가 직접 지정해주어야 한다는 것에 있다.

주어진 데이터를 기반으로 우선순위가 정해지며 우선순위가 정해지는 기준을 사용자가 지정해주는 것이 좋은 자료 구조이다.

자 그럼 우선순위를 정하는 기준의 정보를 담은 함수를 정의하여 함수 포인터로 넘겨주는 식의 구현을 해보자.

1. 구조체 재정의

우선 기존의 힙 구조체를 지우고 함수 포인터를 멤버로 갖는 새로운 힙 구조체를 생성하자.

이 함수 포인터로 전달된 정보를 통해 우선순위를 정할 것이고, 정의 기준은 사용자의 필요에 따라 정한다.

위의 코드를 보면 함수 포인터의 선언과 멤버 선언이 각각 2개로 나누어져 있는데,

typedef로 함수 포인터를 선언하는 두 가지 방법이 있음을 보여주기 위한 것이다.

02. 초기화 함수

초기화 함수에 우선 순위를 정하는 기준에 대한 정보를 담은 함수를 적용시키고 있다.

02. 우선순위가 높은 트리 찾기 함수

원래는 사용자가 정해준 우선숭위에 대한 정보를 통해 처리되었다면

지금은 자용자가 정해준 함수를 통해 우선순위에 대한 처리가 이루어지고 있다.

03. 삽입

삽입 또한 사용자가 지정한 우선순위에 의해 처리되던 기존 방식과는 달리

사용자가 지정한 함수에 의해 우선순위가 가려지며, 새 노드의 위치가 결정되고 있다.

매개변수로 원래는 pr이라는 우선순위 정보가 전달되었지만 지금은 없어졌다.

04. 삭제

삭제 또한 삽입과 마찬가지로 진행된다.

05. 메인

초기화를 할 때 우선순위 기준 정보를 담은 함수를 적용시켜주고 있다.

지금까지 우선순위 큐의 이해와 구현과정에 대해 알아보았다.

다음 부터는 이진 탐색트리에 대해 공부해보도록 하겠다.