안용학 교수님 (2) 썸네일형 리스트형 힙 Heap 개념,우선순위 큐를 이용한 구현 (python)과 성능 비교, 힙 정렬, 상향식 힙 생성, 응용 문제 1. 힙 Heap 내부 노드에 키를 저장하며 다음 두가지 속성을 만족하는 이진트리 힙순서 (heap-order) : 루트를 제외한 모든 내부 노드 v key(v) >= key(parent(v)) 모든 노드의 경우, 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같아야 한다. 완전이진트리 (complete binary tree) : 힙의 높이 h i = 0, ..., h-1에 대하여 깊이 i인 노드가 $2^i$개 존재 깊이 h-1에서 내부노드들은 외부노드의 왼쪽에 존재 즉, 진행순서 : Root - L - R ⇒ 힙의 마지막 노드는 깊이 h-1의 가장 오른쪽 내부 노드 n개의 키를 저장한 힙의 높이 = O(logn) 2. 힙을 이용한 우선순위 큐 구현 각 내부노드에 key-value 쌍을 저장 마지막 .. Priority Queue 우선순위 큐 개념과 이를 이용한 정렬 및 응용 문제 파이썬 구현 1. 우선순위 큐 ADT 각 데이터 항목을 (키, 원소) 쌍으로 저장 ex) (학번, 점수), (주소, 우편물) unordered : 삽입시 데이터 키를 고려하지 않기 때문에 빠르지만 삭제는 키의 순서로 고려해야 해서 느리다. ordered: 삽입시 느리지만 삭제를 빠르다. 삽입 삭제의 빈도에 따라 구현 방식을 결정한다. 삽입시 키에 따라 정렬, 삭제시 키에 따라 정렬 키를 저장하기 위한 자료구조로 우선순위 큐를 활용한다. ADT 메소드 i) 주요 메소드 insertItem(k,e) : 키 k인 원소 e를 큐에 삽입 element removeMin() : 큐에서 최소 키를 가진 원소를 삭제하여 반환 ii) 일반 메소드 int size () : 큐의 항목 수 반환 bool isEmpty() : 큐가 비어있.. 이전 1 다음
