우선순위 큐

우선순위 큐란 우선순위가 높은 데이터대로 먼저 나가는 자료구조이다. 

우선순위 큐에 중요한 연산은 총 2가지가 있는데 , 첫번째는 insert(삽입연산), 두번째는 delete(삭제연산) 이다

우선순위 큐는 2가지로 구분이 되는데 최소 우선순위 큐는 가장 우선 순위가 낮은 요소를 먼저 삭제한다.

최대 우선 순위 큐는 가장 우선순위가 높은 요소가 먼저 삭제된다.

---

 우선순위 큐의 구현방법

표현 방법	삽입	삭제
순서 없는 배열	O(1) {배열 맨끝에 새로운요소를 추가}	O(n) {처음부터 끝까지 모든 요소를 스캔}
정렬된 배열	O(n) {다른 요소의 값을 비교후 삽입}	O(1) {숫자가 높은것이 우선순위가 높다고 가정하면 맨 뒤에 위치한 요소 삭제}
순서 없는 연결리스트	O(1) {첫번째 노드로 삽입}	O(n) {모든 노드를 포인터를 따라서 뒤져봐야한다}
정렬된 연결리스트	O(n){우선순위가 높은 요소가 첫번째 노드로 위치하게 하여 적절한 곳에 연결해야한다}	O(1){첫번째 노드를 삭제하면된다}
히프	O(logn){밑에서 설명}	O(logn){밑에서 설명}

---

히프

히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 

 

히프 트리의 특성상 최대 히프인 경우 key(부모노드) >= key(자식노드)

데이터들은 느슨한 상태로 정렬(큰 값이 상위레벨에 있고 작은 값이 하위레벨에 있다는 정도이다)

히프는 완전이진트리 이다.

 

완전 이진 트리 이기때문에 각각의 노드에 차례대로 번호를 붙일 수 있다. 이 번호를 인덱스로 생각하면 배열에 히프의 노드들을 저장할 수 있다. 배열을 이용하여 히프를 저장하면 자식 노드와 부모노드를 쉽게 알 수 있다.

어떤 노드의 왼쪽이나 오른쪽 자식의 인덱스를 알고 싶다면 다음과 같은 식을 이용하면 된다.

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

// 원칙상 히프트리를 만들 때 배열의 인덱스 0에는 아무 값도 집어넣지 않는다. 

 

struct element{
	int key;
  }
  
  struct HeapType{
  	element heap[200];
  	int heap_size;
  }

---

 

히프의 구현

삽입연산 : 

(1) 새로운 요소 7이 삽입될때 번호순으로 마지막 위치에 삽입된다.

(2) 부모노드 5와 비교하여 삽입노드 7이 더 크므로 교환한다.

(3) 코드 구현

void insert_max_heap(HeapType *h, element item)
{
	int i;
    i = ++(h->heap_size);
    
    //트리의 바닥부터 올라가면서 부모노드와 비교하는 과정
    while((i!=1)&&(item.key > h->heap[i/2].key)){
    h->heap[i] = h->heap[i/2];
    i/=2;
    }
    h->heap[i]=item;

(4) 히프의 시간 복잡도

삽입 연산에서 새로운 요소 히프트리를 타고 올라가면서 부모노드들과 교환을 하게 되는데 최악의 경우 루트 노드까지 올라가야하므로 트리의 높이(logh)에 해당하는 비교연산및 이동연산이 필요하다.

완전이진트리에서의 최대노드 수 n = 2h - 1 이므로 (n+1) = 2h ->  h = log₂(n+1) ≈ log₂n

따라서 O(log₂n) 이다.

 

삭제연산

(1) 먼저 루트 노드가 삭제된다. 빈 루트 노드 자리에는 히프의 마지막 노드를 가져온다.

(2) 가져온 마지막 노드와 루트의 자식노드들을 비교해서 더 큰 노드가 있으면 교환이 일어난다.

(3) 코드 구현

element delete_max_heap(HeapType * h)
{
	int parent,child;
    element item,temp;
    
    //우선순위대로 추출을 위해 루트노드를 가져온다 부모노드 >= 자식노드
    item = h->heap[1];
    //마지막 노드 가져오기
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child =2;
  	while(child <=h->heap_size){
    //가져온 마지막 노드를 루트노드로 하고 그 노드의 자식 노드 중 더 큰 자식노드를 찾는다.
    if((child<h->heap_size)&&(h->heap[child].key < h->heap[child+1].key))
    	child++;
    //가져온 마지막 노드가 자식노드만 크면 반복문에서 나오기
    if(temp.key >= h->heap[child].key) break;
    //한 단계 아래로 이동
    h->heap[parent] = h->heap[child];
    parent = child;
    child*=2;
    }
    //위치가 정해졌으므로 저장
    h->heap[parent] = temp;
    return item;
}

(4) 히프의 시간 복잡도

삭제도 삽입과 마찬가지로 마지막 노드를 루트로 가져온 후에 자식 노드들과 비교하여 교환하는 부분에서 최악의 경우

가장 아래 레벨까지 내려가야하므로 역시 트리의 높이만큼의 시간이 걸린다. 따라서 삭제의 시간복잡도도 O(log₂n)이 된다.

 

---

전체 구현

#include <iostream>
using namespace std;

typedef struct element {
	int key;
};

typedef struct heap {
	element heap_array[200];
	int heap_size;
};
void init(heap *h)
{
	h->heap_size = 0;
}
heap* heap_create(heap *h);
void insert_heap(heap* h, element factor);
element delete_heap(heap* h);

heap* heap_create()
{
	heap* h = new heap;
	return h;
}

void insert_heap(heap* h, element factor) {
	int i;
	i = ++(h->heap_size);
	while ((i != 1) && (factor.key > h->heap_array[i / 2].key)) {
		h->heap_array[i] = h->heap_array[i / 2];
		i /= 2;
	}
	h->heap_array[i] = factor;

}
element delete_heap(heap *h)
{
	int parent = 1;
	int child = 2;
	//우선순위 제일 높은 루트노드 저장
	element rootNode; 
	//우선순위 제일 낮은 노드 저장
	element lastNode;

	rootNode = h->heap_array[1];
	lastNode = h->heap_array[h->heap_size--];
	//밑으로 내려가면서 하나씩 비교
	while (child <= h->heap_size)
	{
		if ((child < h->heap_size)&&(h->heap_array[child].key<h->heap_array[child+1].key)) {
			child = child+1;
		}
		if (lastNode.key >= h->heap_array[child].key) break;


		h->heap_array[parent] = h->heap_array[child];
		parent = child;
		child *= 2;


		
	}
	h->heap_array[parent] = lastNode;
	return rootNode;
	
}

int main() {
	element a = { 3 };
	element a1 = { 1 };
	element a2 = { 9 };
	element a3 = { 7 };

	heap *h;

	h = heap_create();
	init(h);
	insert_heap(h, a);
	insert_heap(h, a1);
	insert_heap(h, a2);
	insert_heap(h, a3);

	//잠시 임시 저장할 곳
	element test;
	int num = h->heap_size;

	//우선순위대로 출력
	for (int i = 0; i <num; i++)
	{
		test = delete_heap(h);
		cout << test.key << " ";

	}

	delete h;
}