우선순위 큐와 힙

 

 

 

---

 

우선순위 큐는 무엇이고
힙은 무엇일까?

 

 

---

 

 

 

 

우선순위 큐(priority queue)

 

--

우선순위 큐는

주어진 점수에 따라 항목을 정렬하여 탐색하는 자료 구조다.

 

기초적인 스택과 큐는

데이터가 삽입된 순서만 고려했지만,

 

우선순위 큐는

추가 정보, 즉 우선순위를 사용해서 탐색 순서를 결정한다.

 

그래서 자료 구조를 데이터에 더 적합하게 적용할 수 있으며,

유용한 응용 분야 중 하나로, 긴급한 요청을 먼저 처리할 수도 있다.

 

 

 

우선순위 큐의 특징

• 항목 집합을 저장하고, 가장 높은 우선순위를 가진 항목을 쉽게 탐색하게 해 준다.
• 우선순위 큐는 동적이며, 삽입과 탐색을 혼용해도 잘 작동한다.
• 우선순위가 지정된 작업 목록에서 항목을 추가하거나 제거 또한 가능해야 한다.

 

 

기본적인 우선순위 큐의 주요 연산 기능

• 항목과 그 항목에 대한 우선순위 점수를 추가
• 가장 높은 우선순위를 가진 항목을 탐색 (큐가 비어 있으면 null 반환)
• 가장 높은 우선순위를 가진 항목을 제거 (큐가 비어 있으면 null 반환)

(우선순위 큐가 비어 있는지 확인하거나 현재 저장된 항목 수를 반환하는 기능도 추가할 수 있다.)

 

 

원시 자료 구조인 정렬된 연결 리스트나 정렬된 배열 같은 자료 구조를 사용해서

우선순위 큐를 구현할 수도 있지만, 이상적인 방법은 아니다.

원시 자료 구조를 사용할 때도 우선순위에 따라 새 항목을 목록에 추가해야 하기 때문이다.

 

 

정렬된 연결 리스트는 우선순위가 가장 높은 항목을 리스트의 맨 앞에 두기 때문에 탐색이 쉽다.

그래서 첫 번째 원소를 확인하기만 하면 우선순위 큐의 길이에 관계없이 상수 시간에 최우선 항목을 탐색할 수 있다.

다만, 새로운 원소를 추가하려면 비용이 많이 들 수 있다.

새 항목을 추가할 때마다 전체 목록을 순회해야 할 수도 있고,

이로 인해 우선순위 큐의 길이에 비례하는 시간이 걸릴 수도 있다.

 

 

물론 정렬하지 않은 연결 리스트나 비열로도 우선순위 큐를 유지할 수도 있다.

정렬하지 않기 때문에 새 항목을 추가하는 것은 단순히 리스트의 뒤에 추가하면 된다.

 

 

다만, 이러한 경우에는 다음 원소를 찾기 위해 높은 비용을 지불해야 한다.

가장 높은 우선순위를 가진 원소를 결정하기 위해 전체 리스트를 스캔해야 하기 때문이다.

게다가 해당 원소를 제거하면 빈 공간을 메우기 위해 모든 원소를 이동시켜야 한다.

 

 

정리

• 우선순위 큐를 사용하는 방식에 따라 정렬한 리스트를 사용하는 것이 정렬하지 않은 리스트를 사용하는 것보다 나을 수도 있고 그 반대일 수도 있다.
• 탐색보다 추가를 자주 하는 경우 = 정렬하지 않은 리스트를 선호
• 탐색을 더 자주하는 경우 = 정렬된 리스트를 선호

이렇게 어느 한 작업을 중시하면 전반적인 비효율이 발생할 수 있으므로,

삽입과 탐색 사이의 비용을 균등화할 방법이 필요하다.

--

 

 

 

 

힙 (heap)

 

--

힙은

완전 이진트리의 일종으로,

각 노드의 키 값이 특정한 규칙을 만족하도록 구성된 자료 구조이다.

 

힙에는 크게 두 가지 종류가 있다.

• 최소 힙(min heap)
• 최대 힙(max heap)

--

 

 

 

 

최대 힙(max heap)

 

--

최대 힙은

노드와 그 자식 노드 간의 특별한 순서를 유지하는 이진 트리의 변형이다.

 

그리고 최대 힙 속성(max heap property)에 따라 원소를 저장한다.

 

최대 힙 속성(max heap property)는
트리의 모든 노드의 값이 자신의 자식 노드의 값보다 크거나 같음을 의미
(부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같아야 한다.  [ 부모 노드의 키 값 >= 자식 노드의 키 값 ])

 

 

위 그림은 최대 힙 속성에 따라 구성한 이진트리 (힙)이다.

 

왼쪽 자식과 오른쪽 자식은 해당 부모보다 우선순위가 낮으면 되고,

둘 사이에 특별한 순서나 우선순위는 없다.

 

최대 힙을 사용할 때 특징

• 사용자가 가장 큰 원소를 효율적으로 조회 가능
• 가장 큰 원소를 효율적으로 제거 가능
• 임의의 원소를 효율적으로 추가 가능

 

 

힙을 트리로 시각화하는 경우가 자주 있지만 효율을 위해 힙을 배열로 구현하기도 한다.

힙의 성질과 배열의 특성을 결합하면 메모리와 연산 효율성을 극대화할 수 있기 때문이다.

 

루트 노드는 항상 최대 힙에서 최댓값에 해당하고, 배열의 고정된 위치(index= 1)에 저장하기 때문에

언제나 상수 시간에 이 최댓값을 찾을 수 있다.

 

그렇다고 꼭 배열을 사용할 필요는 없다.

 

 

임의의 원소를 우선순위 큐에 추가하고 제거할 것이기 때문에
배열 크기를 계속 변경해야 하므로 비용이 많이 든다.
이를 해결하기 위해 처음부터 큰 배열을 할당하여 배열에 마지막으로 채워 넣은 원소의 인덱스를 추적하고,
해당 인덱스를 배열의 실질적인 끝부분이라고 부를 수 있다.

다만 이러한 방법도 힙이 예상한 만큼 커지지 않으면 배열의 남은 공간이 낭비가 되고 과할당이 될 수 있다.

 

 

 

힙에 원소 추가하기

새로운 원소를 힙에 추가할 때는 구조가 힙 속성을 유지하도록 해야 한다.

 

힙에 원소를 추가하는 방법은

힙에 새 원소를 추가하려면 트리의 가장 아래쪽 첫 번째로 비어 있는 공간에 원소를 추가해야 한다.

그리고 나서 추가한 원소와 해당 원소의 부모 노드와 비교하여 부모의 값보다 작을 때까지 두 노드의 위치를 변경해 주는 것을 반복해 준다.

 

 

1. 기존 힙에 새 원소 85를 추가할 예정
2. 트리의 가장 아래쪽 첫 번째로 비어 있는 공간에 원소를 추가
3. 추가한 노드와 해당 노드의 부모 노드와 값을 비교
4. 새로 추가한 노드의 값이 더 크기 때문에 해당 부모 노드와 위치 변경
5. 다시 해당 노드와 부모 노드와 값을 비교
6. 이번에는 부모 노드의 값보다 작기 때문에 그대로 냅두고 완료한다.

 

 

while 루프를 사용한 예시 코드 [JAVA]

public class MaxHeap {
    private int[] heap;		// 힙을 저장하는 배열
    private int size;		// 현재 힙의 크기
    private int capacity;	// 힙의 최대 용량

    // 생성자: 초기 용량을 설정하고 힙 배열을 초기화
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity + 1]; // 1부터 시작하기 위해 +1
        this.size = 0;
    }

    // 힙의 크기를 두 배로 증가시키는 메서드
    private void increaseHeapSize() {
        capacity *= 2; 						// 용량을 두 배로 증가
        int[] newHeap = new int[capacity + 1]; 			// 새로운 배열 생성
        System.arraycopy(heap, 0, newHeap, 0, size + 1); 	// 기존 요소들을 새 배열로 복사
        heap = newHeap; 					// 힙 배열을 새 배열로 교체
    }

    // 힙에 새로운 값을 삽입하는 메서드
    public void insert(int value) {
        
        if (size == capacity) {			// 힙이 가득 찬 경우 크기를 증가
            increaseHeapSize();
        }
        
        size++; 				// 힙의 크기를 증가
        heap[size] = value; 			// 새로운 값을 힙 배열의 끝에 추가

        int current = size; 			// 현재 인덱스
        int parent = current / 2; 		// 부모 인덱스 계산

        // 부모 노드가 존재하고, 부모 노드의 값이 현재 노드의 값보다 작은 경우
        while (parent >= 1 && heap[parent] < heap[current]) {
            int temp = heap[parent]; 			// 부모와 현재 노드의 값을 교환
            heap[parent] = heap[current];
            heap[current] = temp;
            current = parent; 				// 현재 노드를 부모 노드로 변경
            parent = current / 2; 			// 새로운 부모 노드 계산
        }
    }
}

 

1. 우선 힙을 저장하기 위해 배열을 사용하기 때문에 추가할 배열 공간이 있는지 확인 [[ if(size == capacity) ]]
2. 만약 공간이 없으면 배열의 크기를 2배로 늘려준다.
3. 새로운 원소를 배열 끝에 추가한다.
4. 현재 인덱스로 해당 부모 엔덱스까지 계산하여 가져온다.
5. 현재 값과 부모 값을 비교하면서 상황에 알맞게 둘의 위치를 교환하는 것을 반복한다.

 

 

 

힙에서 가장 큰 원소 제거하기

우선순위가 가장 높은 노드를 제거하려면,

먼저 힙 속성을 깨뜨린 다음 다시 복원해야 한다.

 

 

1. 우선순위가 가장 높은 노드 '99'와 최하위 수준의 마지막 노드 '55'와 교환
2. 이렇게 교환하므로 배열 구현에서는 배열 크기의 변화나 공백 없이 그대로 배열이 꽉 찬 상태로 유지된다.
   (+우선순위가 뒤 바뀌면서 힙 속성이 깨짐)
3. 마지막 노드로 된 '99'를 제거한다. 
   (원래 힙의 최댓값인 노드를 제거했지만 그래도 힙 속성이 깨졌을 가능성이 높다.)
4. 새로 정의된 (잘못된)루트 노드 '55'를 힙 속성에 알맞게 위치를 이동하기 위해 자식 노드 중에 가장 높은 노드와 비교하여 현재 루트 노드보다 크다면 두 노드의 위치를 교환하고 루트 노드가 크다면 힙 속성이 유지 중이므로 교환 없이 종료시킨다.  (현재 루트 노드의 자식 노드 중에 가장 큰 노드가 '77'로 루트 노드 '55' 보다 크기 때문에 교환)
5. (교환하여 힙 속성을 다시 복원 중)
6. 4번을 다시 반복하여 현재 노드 '55'와 그 자식 노드 중에 가장 큰 노드 '20'을 비교하여 교환 여부를 판단
   (현재 노드 '55'보다 큰 자식 노드가 없기 때문에 더 이상 교환 반복 중지하여 힙 속성을 복원한 것으로 판단)
7. 힙 속성 복원

 

 

힙에서 최대 원소 제거 예시 코드 [JAVA]

class MaxHeap {
    int[] heap;
    int lastIndex;

    public MaxHeap(int size) {
        heap = new int[size + 1]; // heap[0]은 사용하지 않음
        lastIndex = 0;
    }

    // 최대 원소 제거 메서드
    public Integer heapRemoveMax() {
    
        if (lastIndex == 0) {	// 힙이 비어 있다면
            return null;
        }

        int result = heap[1];	// 최대 원소를 따로 빼놓고
        heap[1] = heap[lastIndex];	// 마지막 인덱스를 루트 노드에 삽입
        heap[lastIndex] = 0; // 마지막 요소를 제거 (최대 원소 제거) (int 배열에는 null삽입 불가)
        lastIndex--;	// 마지막 노드를 가리키는 인덱스 감소

        int i = 1;	// 현재 위치의 인덱스 (1 = 루트 노드 인덱스)
        
        // 힙 속성을 복원하기 위해 while 반복
        while (i <= lastIndex) {
        
            int swap = i;
            
            // 왼쪽 자식노드 인덱스가 마지막 인덱스 이하 & 현재 노드(부모)가 왼쪽 자식노드보다 작으면
            if (2 * i <= lastIndex && heap[swap] < heap[2 * i]) {
                swap = 2 * i;
            }
            // 오른쪽 자식노드 인덱스가 마지막 인덱스 이하 & 현재 노드(위 if문에 해당되었다면 왼쪽 자식 노드)가 오른쪽 자식노드보다 작으면
            if (2 * i + 1 <= lastIndex && heap[swap] < heap[2 * i + 1]) {
                swap = 2 * i + 1;
            }
            // 양쪽 자식과 비교 후 현재 노드보다 더 큰값이 존재했다면 (두 자식 노드중 더 큰 노드와 교환)
            if (i != swap) {
                int temp = heap[i];
                heap[i] = heap[swap];
                heap[swap] = temp;
                i = swap;
            } else {
                break;	// 더 이상 교환하지 않으면 반복분 종료
            }
        }
        return result;
    }
}

--

 

 

 

 

최소 힙 (min heap)

 

--

최소 힙은

최대 힙과 반대로 가장 낮은 점수를 가진 항목을 쉽게 찾기 위한 힙이다.

 

최소 힙에서는

루트 노드가 가장 작은 값으로 사용하기 때문에 해당 항목을 쉽게 찾을 수 있다.

 

이론적으로는 최대 힙에서 값의 부호만 바꾸고 그대로 사용할 수 있지만

더 깔끔한 전략은 힙 속성에 작은 수정을 가해서 문제를 완전히 해결하는 것이다.

 

--

 

 

 

 

힙 정렬

 

--

힙 정렬은

힙 자료 구조를 사용해 원소의 목록을 정렬하는 알고리즘이다.

 

입력은 정렬되지 않은 배열이며 출력은 동일한 원소를 포함하지만 내림차순으로 정렬된 배열이다. (최대 힙의 경우)

 

힙 정렬의 단계

1. 모든 항목에서 최대 힙을 구축
2. 힙에서 모든 항목을 내림차순으로 추출하고 배열에 저장

 

 

힙 정렬 예시 코드 [JAVA]

import java.util.Arrays;

public class HeapSort {
    public static Integer[] heapsort(Integer[] unsorted) {
        int N = unsorted.length;
        MaxHeap tmpHeap = new MaxHeap(N);	// 크기가 동일한 임시 힙 생성
        Integer[] result = new Integer[N];	// 크기가 동일한 배열 생성

        // 배열의 모든 요소를 임시 힙에 삽입
        for (int j = 0; j < N; j++) {
            tmpHeap.heapInsert(unsorted[j]);
        }

        // 힙에서 최대값을 제거하여 해당 최대값을 결과 배열에 삽입
        for (int j = 0; j < N; j++) {
            result[j] = tmpHeap.heapRemoveMax();
        }

        return result;
    }
}

public static void main(String[] args) {
    Integer[] unsorted = {46, 35, 9, 28, 61, 8, 38, 40};
    Integer[] sorted = HeapSort.heapsort(unsorted);
    System.out.println(Arrays.toString(sorted));
}

 

 

배열의 모든 요소를 임시 힙에 삽입(힙 요소 삽입 메서드)하는 과정

 

 

 

최댓값을 제거하면서 해당 최대값을 반환용 배열에 삽입하는 과정

 

이러한 과정을 걸쳐 결과적으로 정렬된 배열을 반환하게 된다.

그리고 힙을 모두 비우고 나면 목적을 달성했으므로 힙을 표현하는 배열을 버린다.

--