[자료구조] 우선순위 큐, 힙

우선순위 큐란?

우선순위의 개념을 큐에 접목시킨 자료구조. 즉 우선순위가 높은 요소가 먼저 들어오고 먼저 나가는 자료구조다.

 

 

구현 방법 선택

우선순위 큐를 구현하는 방법은 배열, 리스트, 힙 3가지가 있는데, 그중 힙이 가장 효율적이다.

 

힙(heap)이란?

- 완전 이진 트리의 일종이며 우선순위 큐를 위해 만들어졌다.

  즉, 각 요소들의 우선순위를 비교하여 트리로 정리해놓은 것이다.

 

- 힙은 최대힙과 최소힙으로 나뉜다.

  최대 힙 : 부모의 값 >= 자식의 값 인 완전 이진 트리

  최소 힙 : 부모의 값 <= 자식의 값 인 완전 이진 트리

 

- 이진 탐색 트리와 다르게 요소의 값이 중복 가능하다

 

 

 

힙의 특징(장점)

- 루트 노드는 모든 노드 중 최대/최소의 값을 가진다.

     - 장점 : 모든 노드 중 최대/최소의 값을 빠르게 찾을 수 있다.

 

 

최대 힙 구현

 

특징 :

- 힙을 저장하는 구조는 배열이다. 배열은 아래와 같이 레벨순회(루트부터 레벨 순서대로 방문) 순서로 정렬한다.

연결리스트로 구현하지 않은 이유 :

         - 연결리스트의 각 노드는 보통 부모->자식으로만 갈 수 있지 자식->부모로는 갈 수 없다. 힙의 노드 생성을 구현하려면 리프 노드에서 생성되어 자식과 부모의 값을 비교하며 위로 올라갈 수 있어야 하는데 연결리스트는 이를 수행하지 못한다.

         - 우선순위 큐는 노드 삭제시 맨 앞의 루트노드만 삭제하므로 삭제 후 빈곳을 채우기 위해 뒤 요소들을 한칸씩 앞으로 옮기지 않는다. 배열은 삭제할 때 한칸씩 앞으로 옮기느라 시간이 오래걸려 문제가 되는데, 이 경우 그런 일이 생기지 않는다.

 

- 배열의 [0] 위치는 쉬운 구현을 위해 비워둔다.

 

 

구현에 활용할 공식들 :

- 자식 노드의 인덱스를 2로 나눈 몫 = 부모의 인덱스

- 부모의 인덱스 * 2 = 왼쪽 자식의 인덱스

- 부모의 인덱스 * 2 +1 = 오른쪽 자식의 인덱스

- 왼쪽 자식의 인덱스 + 1 = 오른쪽 자식의 인덱스

 

 

 

최대 힙 클래스 코드 구현

class MaxHeap{     
public:
    MaxHeap(int theCapacity = 10){
        heap = new int[capacity + 1];
        heapSize = 0;
        capacity = theCapacity;
    }

private:
    int* heap;        //배열
    int heapSize;       //요소의 갯수
    int capacity;       //배열의 크기
};

 

노드 삽입 

- 리프노드에 새로운 값을 삽입하고 최대 힙이 되도록 재정렬하는 함수.

 

연산 과정

(1)->(2) : 리프 노드에 값 삽입

(2)->(3) : 생성한 노드의 값이 부모 노드의 값보다 크면 서로 교환, 크지 않으면 중단

(3)->(4)->... : 루트에 도달할 때까지 (2)->(3)반복  

 

 

 

삽입 구현 코드 

- 구현에 활용한 공식 : 삽입한 노드의 인덱스를 2로 나눈 몫 = 부모의 인덱스

- O(logn)의 시간이 걸린다.

void Push(int& n){
    heap[++heapSize] =  n;        //리프 노드에 값 삽입
    int current = heapSize;             //삽입한 요소의 현 위치
    
    //root에 도달하지 않음 && 삽입한 값 > 부모의 값 이면 true 
    while(current != 1 && heap[current] > heap[current/2]){  
        heap[current] = heap[current/2];
        heap[current/2] = n;
        current /= 2;       //삽입한 요소의 현위치를 부모의 위치로 이동
    }
}

 

노드 삭제

- 루트노드를 삭제한다. (최대 힙은 최대값을, 최소 힙은 최소값을 삭제하게 된다)

 

- 연산 과정

1) 루트 노드 삭제

2) 배열 마지막 인덱스의 값을 루트에 두기

3) 왼쪽 오른쪽 중 값이 큰 자식과 루트와 비교, 자식의 값이 더 큰 경우 서로 자리 바꿈

4) 왼쪽 오른쪽 중 값이 큰 자식과 자리 바뀐 부모와 비교, 자식의 값이 더 큰 경우 서로 자리 바꿈

5) 부모의 값이 자식의 값보다 클때까지 4) 반복

 

 

 

- O(logn) 의 시간이 걸린다.

 

삭제 구현 코드

- 구현에 활용한 공식 :

    - 부모의 인덱스 * 2 = 왼쪽 자식의 인덱스

    - 왼쪽 자식의 인덱스 + 1 = 오른쪽 자식의 인덱스

void Pop() {
    heap[1] = 0;  // 노드 삭제
    int lastE = heap[heapSize--]; // 배열의 마지막 인덱스의 값
    int currentNode = 1;  // 현 노드의 인덱스
    int child =2; // 자식 노드의 인덱스(디폴트는 왼쪽 자식)
    while (child <= heapSize){
        if (child < heapSize && heap[child] < heap[child+1]) child++; //왼쪽자식과 오른쪽자식 비교
        if (lastE >= heap[child]) break;	//부모 > 자식인 경우
        
        heap[currentNode] = heap[child];     // 부모와 자식 자리바꿈
        currentNode = child; 
        child *= 2;
    }
    heap[currentNode] = lastE; 

}