우선순위 큐 & 힙

우선순위 큐?

데이터의 입출력 때 최소한의 비용으로 최우선순위의 데이터를 Head에 위치시키는 알고리즘의 효율을 고민해보쟝!!

- 일단 큐와 같지만 '우선순위' 속성을 갖는 데이터를 다룸!!

   그 우선순위는 프로그래머 마음!

- 연산도 큐 처럼 삽입/삭제

* 힙 Heap

- 자유 저장소의 힙은 아니래!ㅋㅋ

- 힙 순서 속성을 만족하는 완전 이진 트리! (모든 깊이의 노드들이 완전히 채워져 있는 이진 트리)

- 힙 순서 속성 : 트리 내 모든 노드가 부모 노드보다 커야 함!

- 힙에서 루트 노드는 가장 작은 데이터를 갖는 노드!!!!!

- 연산 : 노드 삽입 / 최소값 삭제(루트 삭제)

항상 연산 후에는 힙 순서 속성을 유지하도록!!!!

힙의 구현은 배열을 이용해서!!!

=> 각 노드의 위치나 부모/자식 관계 등을 배열의 인덱스로 파악 가능ㅋㅋ

깊이 순으로 노드 나열ㅋㅋㅋ

typedef int ElementType;

노드

typedef struct tageHeapNode {

ElementType Data;

} HeapNode;

힙 구조체

typedef struct tagHeap {

HeapNode* Nodes;

int Capacity;

int UsedSize;

} Heap;

책에서능 우선순위 큐를 구현할 때 우선순위를 최소값일 수록 높게 잡아놔서

힙을 이용하면 최소값을 얻을 때 효율적!!ㅋㅋ

출처 : 뇌를 자극하는 알고리즘 (한빛미디어)