자료구조 - 우선순위 큐

우선순위 큐(priority queue)는 우선순위를 가진 데이터가 먼저 나가는 형식을 뜻한다.

C++에서는 앞서 구현해본 스택이나 큐를 이용해서 우선순위 큐를 구현할 수 있다.

 

우선순위 큐는 최소 우선 순위큐 / 최대 우선 순위큐로 구분 가능하다.

 

1. 앞서 배열을 이용해서 구현하는 방법,

2. 연결리스트를 이용하는 구현 방법,

3. 그리고 가장 최근에 배운 완전이진트리를 이용한 힙(heap)을 이용한 구현방법이 존재한다.

 

오늘은 3번째 방법으로 최대 힙, 최소 힙을 구현해보겠다.

※여기서 최대 힙이란? 부모 노드의 키값 >= 자식 노드의 키값 인 완전이진트리 // 최소힙은 그 반대

 

힙에서 부모노드와 자식노드의 관계

• 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스 * 2) + 1
• 부모의 인덱스 = 자식의 인덱스 // 2

// HeapNode.h
#include <cstdio>

class HeapNode
{
	int key;
 public:
 	HeapNode(int k = 0) : key(k) { }
    void setKey(int k) { key = k; }
    int getKey() { return key; }
    void display() { printf("%4d", key); }
};

// MaxHeap.h 배열을 이용한 최대 힙 클래스 만들기

#include "HeapNode.h"
#include <cstdio>
#define MAX_ELEMENT 200;

class MaxHeap
{
	HeapNode node[MAX_ELEMENT];
    int size;
public:
	MaxHeap() : size(0) { }
    bool isEmpty() { return size == 0; }
    bool isFull() { return size == MAX_ELEMENT - 1; }
    
    HeapNode& getParent(int i){ return node[i/2]; }
    HeapNode& getLeft(int i){ return node[i*2]; }
    HeapNode& getRight(int i){ return node[i*2 + 1]; }
    
    HeapNode find() { return node[1]; }
    //삽입 연산
    void insert(int key)
    {
    	if(isFull() ) return; //힙이 가득찬경우
        int i = ++size;       // 증가된 힙 크기에서 시작
        
        // 트리를 거슬러 올라가면서 부모노드와 비교
        while( i!= 1 && key>getParent(i).getKey()){
        	node[i] = getParent(i);
            i /= 2; }
        node[i].setKey(key);
     }
     //제거 연산
     HeapNode remove()
     {
     if( isEmpty()) { printf("공백에러"); }
     HeapNode item = node[1]; //루트노드
     HeapNode last = node[size--]; //힙의 마지막노드
     int parent = 1;         // 마지막 노드의 위치를 루트로
     int child = 2;          // 루트의 왼쪽자식 위치확인
     while( child <= size ){         //힙 트리를 벗어나지 않는 동안
     	if(child < size && getLeft(parent).getKey() < getRight(parent).getKey()){
        	child++;}
        if(last.getKey() >= node[child].getKey() ) { break; }
        //한단계 아래로 이동
        node[parent] = node[child]
        parent = child
        child *= 2;
     }
     node[parent] = last;
     return item;
     }
};

위에서 만든 힙구조를 이용한 힙 정렬

// heapsort.h

#include "HeapNode.h"
#include "MaxHeap.h"

void heapSort(int a[], int n)
{
	MaxHeap h;
    for(int i =0; i<n ; i++){
    	h.insert(a[i]);}
    // 최대 힙에서 삭제시 가장 큰값 반환되니 오름차순을 위해 맨앞부터 삭제
    for(int i =n-1, i>=0; i--){
    	a[i] = h.remove()->getKey();}
}