힙(Heap)
부모 노드가 자식 노드보다 우선순위가 높은 속성을 만족하는 트리기반의 자료구조이다.
많은 자료 중 우선순위가 가장 높은 요소를 빠르게 가져오기 위해 사용한다.
<힙 구현>
힙은 노드들이 트리의 왼쪽부터 채운 완전이진트리를 구조를 가지며
부모 노드가 두 자식노드보다 우선순위가 높은 값을 위치시킴
힙 상태를 만족하는 경우 가장 최상단 노드가 모든 노드 중 우선순위가 가장 높음
2
┌───────┴───────┐
8 52
┌───┴───┐ ┌───┴───┐
13 37 67 92
┌─┴─┐ ┌─┘
17 43 52
<힙 노드 삽입>
1. 힙의 최고 깊이, 최우측에 새 노드를 추가
2
┌───────┴───────┐
8 52
┌───┴───┐ ┌───┴───┐
13 37 67 92
┌─┴─┐ ┌─┴─┐
17 43 52 (7)
2. 삽입한 노드와 부모 노드를 비교하여 우선순위가 더 높은 경우 교체
2 2 2
┌───────┴───────┐ ┌───────┴───────┐ ┌───────┴───────┐
8 52 8 52 (7) 52
┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐
13 37 67 92 13 (7) 67 92 13 8 67 92
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
17 43 52 (7) 17 43 52 37 17 43 52 37
3. 더이상 교체되지 않을때까지 과정을 반복
2 2
┌───────┴───────┐ ┌───────┴───────┐
(7) 52 7 52
┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐
13 8 67 92 13 8 67 92
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
17 43 52 37 17 43 52 37
<힙 노드 삭제>
1. 최상단의 노드와 최우측 노드를 교체한 뒤 최우측 노드를 삭제
(2) (37) (37)
┌───────┴───────┐ ┌───────┴───────┐ ┌───────┴───────┐
7 52 7 52 7 52
┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐
13 8 67 92 13 8 67 92 13 8 67 92
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┘
17 43 52 (37) 17 43 52 (2) 17 43 52
2. 교체된 노드와 두 자식 노드를 비교하여 우선순위가 더 높은 노드와 교체
(37) 7 7
┌───────┴───────┐ ┌───────┴───────┐ ┌───────┴───────┐
7 52 (37) 52 8 52
┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐
13 8 67 92 13 8 67 92 13 (37) 67 92
┌─┴─┐ ┌─┘ ┌─┴─┐ ┌─┘ ┌─┴─┐ ┌─┘
17 43 52 17 43 52 17 43 52
3. 더이상 교체되지 않을때까지 과정을 반복
7 7
┌───────┴───────┐ ┌───────┴───────┐
8 52 8 52
┌───┴───┐ ┌───┴───┐ => ┌───┴───┐ ┌───┴───┐
13 (37) 67 92 13 37 67 92
┌─┴─┐ ┌─┘ ┌─┴─┐ ┌─┘
17 43 52 17 43 52
<힙 구현>
힙의 완전이진트리 특징의 경우 배열을 통해서 구현하기 좋음
노드의 위치를 배열에 순서대로 저장
노드가 위치한 인덱스에 연산을 진행하여 노드 이동이 가능
부모로 이동 : (index - 1) / 2
왼쪽자식으로 이동 : 2 * index + 1
오른쪽자식으로 이동 : 2 * index + 2
0
┌───┴───┐
1 2 ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
┌─┴─┐ ┌─┴─┐ => │0│1│2│3│4│5│6│7│8│9│
3 4 5 6 └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌┴┐ ┌┘
7 8 9우선순위큐(PriorityQueue)
정해진 순서보다 기준에 따라 우선순위를 정하는 것이 적합한 경우
//입력 순서대로 출력하는 Queue를 사용했을 때
Queue<string> queue = new Queue<string>();
queue.Enqueue("환자1 - 감기");
queue.Enqueue("환자2 - 타박상");
queue.Enqueue("환자3 - 심장마비");
//입력 순서대로 처리
while (queue.Count > 0)
{
Console.WriteLine(queue.Dequeue()); //output: 환자1 - 감기, 환자2 - 타박상, 환자3 - 심장마비
}
//기준에 따라 우선순위대로 처리하는 PriorityQueue를 사용했을 때
PriorityQueue<string, int>priorityQueue = new PriorityQueue<string, int>();
//priorityQueue.Enqueue(Value, Key);
priorityQueue.Enqueue("환자1 - 감기", 5);
priorityQueue.Enqueue("환자2 - 타박상", 8);
priorityQueue.Enqueue("환자3 - 심장마비", 1);
priorityQueue.Enqueue("환자4 - 교통사고", 3);
//각 증상에 따라 등급을 매겨 순서대로 처리
for (int i =0;i<3;i++)//3번 출력
{
Console.WriteLine(priorityQueue.Dequeue());//output: 환자3 - 심장마비,환자4 - 교통사고,환자1 - 감기
}
priorityQueue.Enqueue("환자3 - 심장마비", 1);//중간에 추가 입력
while (priorityQueue.Count > 0)//전부 출력
{
Console.WriteLine(priorityQueue.Dequeue());//output: 환자3 - 심장마비, 환자2 - 타박상
//중간에 추가 입력해도 우선순위대로 출력
}
Console.WriteLine(priorityQueue.Peek()); //다음 우선순위 확인
// 오름차순 : 기본 int 우선순위
PriorityQueue<string, int> pq1 = new PriorityQueue<string, int>();
pq1.Enqueue("Data1", 1);
pq1.Enqueue("Data7", 7);
pq1.Enqueue("Data5", 5);
pq1.Enqueue("Data3", 3);
pq1.Enqueue("Data9", 9);
for (int i = 0; i < 3; i++)
{
Console.WriteLine(pq1.Dequeue()); // output : Data1, Data3, Data5
}
pq1.Enqueue("Data4", 4);
pq1.Enqueue("Data2", 2);
pq1.Enqueue("Data6", 6);
pq1.Enqueue("Data8", 8);
while (pq1.Count > 0)
{
Console.WriteLine(pq1.Dequeue()); // output : Data2, Data4, Data6, Data7, Data8, Data9
}
// 내림차순 : int 우선순위에 * -1을 적용하여 사용
PriorityQueue<string, int> pq2 = new PriorityQueue<string, int>();
pq2.Enqueue("Data1", -1);
pq2.Enqueue("Data7", -7);
pq2.Enqueue("Data5", -5);
pq2.Enqueue("Data3", -3);
pq2.Enqueue("Data9", -9);
for (int i = 0; i < 3; i++)
{
Console.WriteLine(pq2.Dequeue()); // output : Data9, Data7, Data5
}
pq2.Enqueue("Data4", -4);
pq2.Enqueue("Data2", -2);
pq2.Enqueue("Data6", -6);
pq2.Enqueue("Data8", -8);
while (pq2.Count > 0)
{
Console.WriteLine(pq2.Dequeue()); // output : Data8, Data6, Data4, Data3, Data2, Data1
}<우선순위큐(PriorityQueue) 기능구현>
namespace DataStructure
{
//우선순위큐 클래스<일반화>
//우선순위는 비교가 필요하기 때문에 where TPriority : IComparable<TPriority>
public class PriorityQueue<TElement, TPriority> where TPriority : IComparable<TPriority>
{
private struct Node //배열로 구현하기 위해 구조체로 Node 생성
{
public TElement element; //데이터
public TPriority priority; //우선순위
public Node(TElement element, TPriority priority)//생성자
{
this.element = element;
this.priority = priority;
}
}
private List<Node> nodes;
public PriorityQueue() //생성자
{
nodes = new List<Node>(); //리스트 생성
}
public int Count { get { return nodes.Count; } }
public void Enqueue(TElement element, TPriority priority)//입력함수 구현
{
Node newNode = new Node(element, priority);
nodes.Add(newNode); //리스트에 새 노드 입력
int index = nodes.Count - 1; //인덱스 위치는 리스트의 갯수-1
while (index > 0) //인덱스0(최상단)에 도착하기 전까지 반복
{
int parentIndex = (index - 1) / 2; //부모 인덱스 위치
Node parentNode = nodes[parentIndex]; //부모 값을 parentNode에 입력
if (newNode.priority.CompareTo(parentNode.priority) < 0)
//새 노드의 우선순위와 부모의 우선순위를 비교했을 때 더 작다면
{
//새노드가 상단으로 올라가야 한다.
nodes[index] = parentNode; //부모노드를 새 노드 위치에 입력
nodes[parentIndex] = newNode;//새 노드를 부모 노드 위치에 입력
index = parentIndex; //인덱스 상승
}
else //부모가 더 우선순위가 높을 때
{
break;//반복 중지
}
}
// nodes[index] = newNode;
}
public TElement Peek() //다음 출력 확인
{
if (nodes.Count == 0)
throw new InvalidOperationException();
return nodes[0].element;
}
public TElement Dequeue() //출력함수 구현
{
if (nodes.Count == 0)
throw new InvalidOperationException();
Node rootNode = nodes[0];//root 노드를 변수에 보관
//제거 작업
Node lastNode = nodes[nodes.Count - 1];//마지막노드 변수에 보관
nodes[0] = lastNode; //마지막 노드 root노드 위치에 입력
nodes.RemoveAt(nodes.Count - 1);//마지막노드 제거
int index = 0;//인덱스 위치 최상단
while (index < nodes.Count)// 인덱스가 마지막 위치까지 반복
{
int leftIndex = 2 * index + 1; //왼쪽 자식노드 인덱스 위치
int rightIndex = 2 * index + 2; //오른쪽 자식노드 인덱스 위치
if (rightIndex < nodes.Count)//자식이 둘 다 있는 경우
{
int lessIndex;
if (nodes[leftIndex].priority.CompareTo(nodes[rightIndex].priority) < 0)
//왼쪽 인덱스 우선순위와 오른쪽 인덱스 우선순위를 비교해서 더 작다면
{
lessIndex = leftIndex;//왼쪽 인덱스를 작은인덱스 변수에 입력
}
else//반대일 경우
{
lessIndex = rightIndex;//오른쪽 인덱스를 작은인덱스 변수에 입력
}
Node lessNode = nodes[lessIndex]; //작은 인덱스 노드 값을 작은노드변수에 입력
if ((nodes[index].priority.CompareTo(nodes[lessIndex].priority) > 0))
//현재 인덱스 우선순위와 작은 인덱스 우선순위를 비교해서 더 크다면
{
nodes[lessIndex] = lastNode;//마지막노드에서 가져온 값을 작은 인덱스 위치에 입력
nodes[index] = lessNode; //작은 인덱스 노드 값을 최상단 인덱스 위치로 입력
index = lessIndex; //작은인덱스 위치를 현재 인덱스로 변경
}
else //현재 인덱스가 자식인덱스보다 작을 때
{
break; //반복 종료
}
}
else if (leftIndex < nodes.Count)//자식이 하나만 있는 경우
{
Node leftNode = nodes[leftIndex];//왼쪽 자식노드의 값을 변수에 입력
if (nodes[index].priority.CompareTo(nodes[leftIndex].priority) > 0)
//현재노드의 우선순위와 왼쪽자식노드의 우선순위를 비교했을 때 크다면
{
nodes[leftIndex] = lastNode; //마지막 인덱스에서 가져온 값을 왼쪽인덱스에 입력
nodes[index] = leftNode;//왼쪽노드를 현재 인덱스에 입력
index = leftIndex;//왼쪽자식인덱스를 현재인덱스로 변경
}
}
else //자식이 없는 경우
{
break;//반복 종료
}
}
return rootNode.element;//보관한 root노드 출력
}
}
}
기록하는 것이 기억된다.