GeniusForCE GeniusForCE

히프(Heap)란?▶ 우선순위 큐를 위해 만들어진 자료구조▶ 히프란 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리 (complete binary tree) 최대 히프(max heap)▶ 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리▶ key(부모 노드) ≥ key(자식 노드) 최소 히프(min heap)▶ 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리▶ key(부모 노드) ≤ key(자식 노드) 히프(heap)의 높이▶ n개의 노드를 가지고 있는 히프의 높이는 logn▶ 히프는 완전 이진 트리 (complete binary tree)▶ 마지막 레벨 h을 제외하고는 각 레벨 i에 2^i-1개의 노드 존재 히프의 구현방법히프는 배열..

우선순위 큐(priority queue)▶ 우선순위를 가진 항목들을 저장하는 큐(queue)▶ FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다.자료구조삭제되는 요소스택가장 최근에 들어온 데이터 (LIFO)큐가장 먼저 들어온 데이터 (FIFO)우선순위 큐가장 우선순위가 높은 데이터 환자 치료의 예시를 들어보자.▶ 큐: 먼저 온 사람을 먼저 치료▶ 스택: 나중에 온 사람을 먼저 치료▶ 우선순위 큐: 위급한 사람을 먼저 치료 우선순위 큐(priority queue)는 가장 일반적인 큐임.스택(stack)이나 FIFO 큐를 우선순위 큐로 구현할 수 있다. 우선순위▶ 시간: 스택, 큐▶ 스택, 큐에서는 시간에 따라 자료구조를 조직화▶ 다른 가치: 우선순위 큐▶ 따라서 우선순위 큐는 스택이나 큐..