PS

힙 : 내부노드에 키를 저장하고 루트를 제외한 모든 내부노드 v에 대해 key(v)≥key(parent)[힙순서]를 만족하는 완전이진트리로 구현된 데이터구조 마지막 노드 : 힙의 높이를 h라 하면 깊이 h-1의 가장 오른쪽 내부노드 힙의 높이 : n개의 키를 저장한 힙의 높이는 O(log n)힙을 이용한 우선순위 큐 구현: 우선순위 큐는 리스트 혹은 힙으로 구현 가능: 우선순위 큐의 역할을 구현하려면, 데이터항목의 삽입과 삭제가 자유로운 저장소로 삭제의 경우 최소 키를 가진 항목을 삭제해야 함 저장소로서의 역할 : 힙을 구성하는 적정이진트리 내부노드에 (키, 원소)쌍의 데이터 저장 / 편의상 외부노드에는 데이터 저장 x / 마지막 노드의 위치를 변수로 관리 삽입과 삭제의 역할 삽입 ( InsertItem..

우선순위 큐 ADT : 임의의 데이터 항목이 삽입되며, 일정한 순서(우선순위가 높은 원소부터 삭제)에 의해 삭제되는 데이터 구조. '큐'와 데이터 항목을 저장하고 삽입과 삭제가 가능하다는 점은 동일.- 우선순위 큐에 저장되는 각 데이터 항목은 (키, 원소)쌍으로 정의됨 ex. 우편물의 경우 (주소, 우편물) / 답안지의 경우(학번, 점수) 우선순위 큐 구현방식1) 단순 리스트 사용2) 힙(heap) 사용구현 방식삽입 시간복잡도삭제 시간복잡도리스트O(1)O(n)힙(heap)O(log n)O(log n)우선순위 큐 ADT 메쏘드 1) 주요 메쏘드 insertItem(k,e) : 키 k인 원소 e를 큐에 삽입elemet removeMin() : 큐로부터 최소 키를 가진 원소를 삭제 , 반환 2) 일반 메쏘드i..