힙

Heap  : 힙은 각 노드의 key값을 저장하고 다음의 특성들을 만족하는 이진트리이다.     Heap's Property   1. Heap-order(순서조건) : 루트를 제외한 모든 internal node에 대해  key(v) >= key(parent(v)) 만족 → sibling node끼리는 상관 없음! 이진'탐색'트리일 필요 없음    2. Complete Binary Tree(구조조건)  - 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드이다. → 왼쪽 노드부터 삽입. 오른쪽 노드만 존재하는 노드가 있다면 해당 트리는 완전이진트리가 아님   Height of a Heap : n개의 key를 갖고 있는 힙은 height(O(logn)) 을 갖는다.   ※ 증명 heap 의 높이만큼의 수행횟..

Priority Queue 큐는 먼저 삽입되는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. : 우선순위 큐는, 삽입 순서가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 구현 방식에 따라 running-time이 달라질 수 있다.     Sequeunce-based priority queue(시퀀스 기반 우선순위 큐)1. Selected List(선택정렬) O(n^2): 1.unsorted list와 함께 구현되는 우선순위 큐 방식→ 무순리스트S → 우선순위 큐 P- 우선순위 큐에서 삭제할 때 모든 원소를 비교- 우선순위 큐에 삽입 하는 데 n개의 원소 삽입하므로 O(n)-time- 정렬순서로 삭제하는 데 n + (n-1) + ```  + 1 s..