목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까

[주제]- 앞서 구현한 힙 구조에서 일부분 업그레이드하기 [변경되는 부분]- 프로그래머가 우선순위 판단 기준을 설정해놓기- 우선순위 비교 함수를 만들어서 우선순위 비교하기 [중요]- 우선순위 비교 함수의 기능1. 첫 번째 인자의 우선순위가 높으면: '0'보다 큰 값을 반환2. 두 번째 인자의 우선순위가 높으면: '0'보다 작은 값을 반환3. 각 인자의 우선순위가 동일하면: '0'을 반환 [소스]■ UsefulHeap.h#ifndef SIMPLEHEAP_H_#define SIMPLEHEAP_H_ #define TRUE 1#define FALSE 0 #define HEAP_LEN 100 /* * 'Heap' 구조체에 통합 *//*typedef struct _heapElem{ int pr; char data;..

[배열 기반의 힙 구현]- 연결 리스트 기반으로 구현 시 새로운 노드를 '마지막 위치'에 추가하는 것이 쉽지 않음- 각 노드마다 고유번호가 존재하며, 그 번호가 배열의 인덱스와 동일 ■ 그림(배열 기반의 힙)- 노드 인덱스와 배열 인덱스와 동일하게 만들기 위하여 배열의 0번째는 사용하지 않음 [고유 번호(인덱스)를 통해 부모/자식노드 구하기 규칙]- 왼쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2- 오른쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2 + 1- 부모노드의 인덱스: 자식노드의 인덱스 / 2 ※ 소수점을 무시하고 정수로 몫을 계산 [힙 구현의 개념 및 규칙]- 힙은 완전 이진 트리로 구성됨- 노드 번호와 배열의 인덱스는 동일하며, 마지막 노드 번호는 존재하는 노드의 개수와 동일한 개념으로 판..

[힙의 데이터 저장과정]- '최소 힙'을 기준으로 설명 ※ 데이터의 저장 값이 낮은 것이 우선순위가 높음 - 자식 노드 데이터의 우선순위 ≤ 부모 노드 데이터의 우선순위- 새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장 ※ 마지막 위치: 트리의 마지막 레벨의 가장 오른쪽 - 그리고 부모 노드와 우선순위를 비교해가면서, 해당 우선순위 위치를 찾을 때까지 거슬러 올라가면서 교환을 반복 ■ 그림(추가과정) - 완전 이진 트리 예시 - 새로운 노드가 마지막 위치에 생성됨 - 부모 노드와 우선순위 비교- '2 > 10' 우선순위가 더 높으므로 위치 교환 - 다시 부모 노드와 우선순위 비교- '2 > 3' 우선순위가 더 높으므로 위치 교환 - 다시 부모 노드와 우선순위 비교- '2 < 1' ..

[우선순위 큐의 개념]- 기존 큐와 다르게 데이터가 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 꺼내짐- 데이터에 우선순위가 별개로 지정되지 않으며 값을 기준으로 순서가 동적으로 지정 ※ 데이터 값의 오름차순 또는 내림차순으로 기준을 잡을 수 있으며, 개발자가 결정 - 구현 방법에는 '배열, 연결 리스트, 힙'이 있음 [배열과 연결 리스트 구현 시 문제점] ■ 배열- 데이터의 우선순위가 높을수록 배열의 앞쪽에 위치시킴- 우선순위가 높은 데이터의 반환과 소멸이 쉬움★ 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 앞으로 또는 뒤로 옮기는 연산이 필요★ 삽입의 위치를 찾기 위해서 모든 데이터와 우선순위를 비교하면서 진행해야 함 ■ 연결 리스트★ 배열과 다르게 데이터 위치를 옮기는 작업은 없으..