자료구조
-
Priority Queue자료구조 2019. 9. 2. 16:44
Max priority queue: root의 값이 가장 크고 자식의 값은 부모보다 작거나 같은 Tree Min priority queue: root의 값이 가장 작고 자식의 값은 부모 보다 크거나 같은 Tree empty(), size(), insert(), top(), delete()등의 기능이 있음 empty(), size(), top()은 O(1), insert()와 delete()는 O(logn) Binary 형태의 Priority queue는 Heap Sort에 사용됨 (Average, best, worst O(nlogn) Job Scheduling Problem에서 LPT algorithm 에 사용됨 (Max priority queue로 가장 긴 일을 골라 Min priority queue로..
-
Tree자료구조 2019. 9. 2. 16:07
Arithmetic expression을 Tree로 표현 Prefix - 연산자가 앞 ex) a+b -> +ab Infix - 연산자가 중간 ex) a+b Postfix - 연산자가 뒤 ex ) a+b -> ab+ Infix는 컴퓨터에서 Parsing이 어려워(Tiebreaker, Delimiter등 필요) Prefix나 Postfix로 표현함 Postfix로 표현했을 경우 식을 왼쪽부터 오른쪽으로 읽어나가며 피연산자는 stack에 저장, 이 후 연산자가 나오면 스택에서 피연산자를 꺼내 연산하면 됨 Infix를 Postfix로 바꾸려면 식을 왼쪽에서 오른쪽으로 읽어나가면서, 피연산자는 그대로 Postfix식에 적음 ( 연산자는 연산자 stack에 push ) 연산자가 나오면 (가 나올 때 까지 stack..