[📗c언어 쉽게 풀어쓴 자료구조9] 우선순위 큐

👑 우선순위 큐 소개와 구현

: 우선순위가 높은 데이터가 먼저 나감

& 구현방법
1. 배열

• 정렬 되어있는 경우: 삽입 (O(n)), 삭제(O(1))
• 정렬 되어있지 않은 경우: 삽입 (O(1)), 삭제(O(n))

2. 연결리스트

• 정렬 되어있는 경우: 삽입 (O(n)), 삭제(O(1))
• 정렬 되어있지 않은 경우: 삽입 (O(1)), 삭제(O(n))

3. 히프

👑 히프의 개념

: 완전이진트리로, 우선순위 큐를 위해 만들어진 자료구조임

• 느슨한 정렬 상태, 중복값 허용
• 배열로 저장 (인덱스 0은 사용되지 않음)
• 왼쪽 자식의 인덱스: 부모의 인덱스*2
• 오른쪽 자식의 인덱스: 부모*2+1
• 부모의 인덱스: 자식의 인덱스/2

& 히프의 조건
1. 완전이진트리
2. 부모노드 >= 자식노드

& 히프의 종류
1. 최대 히프
2. 최소 히프: 작을수록 루트로

👑 히프의 구현 (삽입, 삭제)

• 삽입: 마지막 노드에 삽입 후, 재구성 (히프의 조건 만족하도록) / O(logn)- 재구성해서 높이만큼 올라감
• 삭제: 루트 노드 반환 후, 마지막 노드 루트로 가져와서 강등시킴 / O(logn)- 마지막 꺼 가져와서 높이만큼 강등시킴

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200
typedef struct {
	int key;
}element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;
}HeapType;

//생성함수
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}

//초기화 함수
void init(HeapType* h) {
	h->heap_size = 0;
}

//삽입 함수(최대 히프)
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;
}

//삭제 함수(최대 히프)- 부모를 끌어내린 후 마지막에 대입 그리고 반환
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) {  //heap 사이즈 이내일 때 반복
		if ((child < h->heap_size) && (h->heap[child].key) < h->heap[child + 1].key) //큰 자식 선택(오른쪽이 더 크면 +1)
			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;
}

👑 히프 정렬과 시간 복잡도

: 최대 히프 정렬을 통해 O(nlogn) 시간 안에 정렬
-> 최대 히프를 통해 삽입 후, 하나 씩 삭제하면서 배열의 맨 끝 값에 넣어주고, 하나 씩 출력해주면됨.

• 가장 큰 값을 몇 개만 필요로할 때 유용

👑 허프만 코드

: 빈도수 높은 글자에 작은 크기의 코드 할당 (작은것끼리 합치기)

⭕ TIL (Today I learned)

& 배운 내용 내 언어로 정리하기
우선순위 큐는 우선순위가 높은 것을 먼저 빼내는 큐이다. 우선순위큐는 배열, 연결리스트 히프를 통해 구현할 수 있고, 배열이나 연결리스트가 정렬되어 있느냐 아니냐에 따라 시간복잡도가 달라진다. 히프는 우선순위 큐를 위해서 만들어진 자료구조로, 완전 이진트리이며 최대 히프의 경우에는 부모노드가 항상 자식노드보다 크거나 같아야한다. (중복값 허용) 최소 히프의 경우에는 부모노드가 항상 자식노드보다 작거나 같아야하는 것이다. 히프의 삽입 연산은 맨 마지막 노드에 삽입 후 재구성을 해주는 것이고, 삭제 연산은 맨 루트를 반환 후, 마지막 꺼를 루트로 끌어와서 강등시키는 것이다. 이 히프를 이용해서 정렬을 할 수 있다.(히프 정렬) 삽입연산을 통해 삽입 후, 최대 히프를 통해 삭제를 하며, 배열의 마지막 인덱스에 넣는 것이다. 또 이러한 히프를 이용한 것이 허프만 코드인데, 이는 가장 빈도수가 높은 글자에 작은 코드를 부여하는 것이다.