우선순위 큐와 자료구조 힙

우선순위 큐

 

 우선순위 큐는 들어온 순서에 상관없이 우선순위에 초점을 두어 처리하는 큐이다.

 

일반적인 큐나 스택은 이 우선순위 큐에 대해서서, 데이터가 입력 된 시간에 초점을 둔 경우라 볼 수 있다.

 

우선순위 큐 에서는 입력된 데이터에 Tag 값이 필요하다. 이것은 각 데이터 간에 우선순위를 결정하기

 

위해서 비교 되는 수치이다. 따라서 이러한 Tag 값은 곧 우선순위 값(Priority Value) 에 해당하며,

 

이 값을 큐의 키 값으로 한다.

 

배열에 의한 구현

데이터를 삽입 시에, 이진탐색을 통해서 위치를 정하게 되면, 매번 정렬된 결과를 낳는다.

 

데이터가 정렬이 되어있기 때문에 가장 마지막에 있는 값이 바로 우선순위가 가장 큰 값이므로

 

가장 마지막 데이터를 항상 꺼내주면 된다.

 

삽입 시의 효율로 자리를 찾게 되고, 그 자리에서부터 다른 데이터들을 뒤로 전부 1칸씩

 

밀어야 하게 때문에 추가로 의 시간이 든다.

 

결국 삽입 과정은 삭제 시 의 효율이다.

 

연결리스트에 의한 구현

항상 헤드포인터를 최댓값으로 유지하며, 그 이후로 내림차순으로 연결한다.

삽입 시 헤드부터 출발하여 자신의 위치를 찾아간다. 따라서 이 과정에서 최악의 경우

N 개의 데이터를 전부 다 비교해야 한다.

여기서 배열과 다르게 찾은 곳에서 메모리 이동이 없다.(포인터 끼리 연결만 하면 되므로...)

삭제 시에 헤드포인터만 삭제하면 된다. (헤드 포인터를 최대 우선순위로, 내림차순 정렬했기 때문)

 

삽입 과정 

 

삭제 과정 

 

이진탐색트리에 의한 구현

가장 큰 값은 오른쪽으로만 따라 내려가면 만날 수 있다.

 

따라서 삭제과정은 이다.

 

삽입 과정은 이진탐색트리의 삽입과정과 동일하므로

에 가깝다. 항상 트리가  균일한 형태의 모양이라고 가정 했을 때

 

삽입 과정 

 

삭제 과정 

 

힙에 의한 구현

힙(Heap) 의 정의는 다음과 같다.

 

1. 항상 완전이진트리의 형태이다.

2. 부모 노드와 항상 자식노드간의 대소 관계가 성립한다.

3. 부모의 키 값이 더 큰 힙은 최대 힙(Max Heap) 부모의 키 값이 더 작은 힙은 최소 힙(Min Heap) 이라 한다.

 

힙 이란 최대, 최소값을 빠르게 찾을 수 있도록 고안된 자료구조로서, 완전이진트리의 형태를 기반으로 한다.

완전이진트리는 배열로 표시하는 것이 효율 적이므로, 항상 배열로 구현된다.

인덱스 k 에 있는 노드의 왼쪽 자식은    2k + 1

                       .오른쪽 자식은  2k + 2

                            .부모는         (k - 1) / 2

힙의 삭제

 가장 우선순위가 높은 노드는 루트노드이다. 따라서 루트노드를 바로 삭제하는 것은

 배열로 구성한 힙을 또다시 재구성해야 하므로 복잡해진다.

 

 이를 쉽게 해결 하는 방법은 다음과 같다.

 

 1. 루트노드를 삭제하는 대신 가장 말단노드를 루트노드에 복사시킨다.

 2. 다시 힙의 모양을 찾기 위해서, 루트에 복사된 말단 노드가 아래로 자신의 자리를 찾아간다.

    두 개의 자식들 중 우선순위가 가장 큰 값과 서로 스왑 하면서 자신의 자리를 찾아간다.

 3. 만약 자식들 보다 우선순위가 크다면 그 자리가 자신의 자리이다.

 

 

힙의 삽입

 루트부터 시작해서 자신의 자리를 찾아가려고 해도, 힙은 약한 정렬이기 때문에

 왼쪽으로 갈지 오른쪽으로 갈지 선택 할 수 없다. 부모와 자식 간에 대소 관계만 있을 뿐이다.

 따라서 배열의 가장 마지막으로 보낸 다음, 능력껏 자신의 자릴 찾아 올라가도록 하면 된다.

 

• 우선순위 큐, 알고리즘 효율 비교(빅 오)

	삽 입(Insert)	삭 제(Remove)
배열로 구현	N	1
연결 리스트로 구현	N	1
이진 탐색트리로 구현	logN	logN
힙에 의한 구현	logN(보장)	logN(보장)

힙은 완전이진트리 이기 때문에 항상 균형이 유지되는 이진트리이다.

따라서 삽입 삭제의 효율이 항상 logN 으로 보장된다 할 수 있다.

또한 이진탐색트리로 구현 했을 경우 가장 우선순위가 높은 값을 찾는데 걸리는 시간은 이다

 

하지만 힙은 배열의 가장 앞이 가장 우선순위가 높은 노드이다.

따라서 탐색속도는 이다.

 

 

 

힙 정렬

힙 정렬은 힙을 정렬목적으로 사용 한 것이다.

 

힙에서 삭제작업을 하게 되면, 우선순위가 가장 큰 것이 먼저 나온다.

만약 힙이 맥스 힙이었다면 이것을 그대로 받아 적었을 대 내림차순 정렬이 된다.

 

오름차순 정렬을 하고자 한다면, 삭제작업의 결과값을 역순으로 적어가던가 힙을 민 힙으로 구성하면 된다.

힙 정렬을 하기위해서 가장 먼저 해야할 일은 힙의 구성이다. 일단 힙이 완성이 되어야 빼내오면서 정렬을 할 수 있다.

 

 

하향식 힙 구성

 단순하게 힙에 삽입작업을 가한 뒤에, 하나씩 삭제하면서 우선순위가 높은 것부터 꺼내오면서 정렬한다.

 삽입작업을 하게 될 때 힙 이 구성되므로, 하향식이라 한다.

 

 

상향식 힙 구성

 힙의 구성과 상관없이 일단 배열에 모든 데이터를 정렬되지 않을 채로 나열한다.

 이후, 배열에 있는 데이터들을 가지고 힙 구조를 복원한다. 복원하는 과정은 다음과 같다.

 

 가장 마지막 노드부터 역순으로 접근하며, 자신의 자식과 값을 비교해서 대소 관계에 따라

 스왑을 진행하고, 루트 노드에 도달하면 종료한다.

 

힙 정렬의 효율

 하향식 힙 구성 방식은, 힙 구조를 만드는데 

의 효율을 보이는 반면에,  상향식 힙 구성 방식은

의 효율을 보인다. 하지만 이것은 힙을 구성하는데에 걸리는 시간이지 결과적으로

두 방식 모두 정렬을 위한 삭제단계에서  의 효율을 보이므로

두 방식 모두 힙 정렬의 효율은 이다.

 

 쾌속정렬(퀵 소트)은 빠르지만 의 효율을 항상 보장하지 못한다.

 최악의 경우(이미 정렬된 경우) 피벗의 문제가 있기 때문이다.

 

합병정렬은 의 효율을 보장하지만 추가적인 메모리가 필요하다.

 

이런 의미에서만 본다면 항상 의 효율을 보장하며 추가적인 메모리가

필요로 하지 않는 힙정렬이 가장 빨라 보이지만,

실제 구현상의 처리(힙 구조) 때문에 일반적으로 쾌속정렬보다 느리다.