분류 전체보기142 [Heap]32. Vector(array) Based Heap 구현 목차 1. class Heap 2. def swap 3. def upheap 4. def downheap 5. def insert, pop 6. def top, size, print 7. 테스트 1. class Heap class Heap: def __init__(self, dir: int): # 1 입력받으면 min-heap, -1 입력받으면 max-heap """heap을 생성하는 class입니다. Args: dir (int): 1이면 mean-heap, -1이면 max-heap """ self.array = [-1] # 0번째 index값은 사용 안함 self.dir = dir def is_empty(self)-> bool: # heap의 빈 여부 반환 return len(self.array)==1.. 2021. 2. 28. [Heap]31. Vector(array) Based Heap(벡터(배열)기반 힙) 목차 1. Vector(array) Based Heap 1. Vector(array) Based Heap Heap(힙)은 Complete Binary Tree이기 때문에, 배열 혹은 벡터에 충분히 저장 가능합니다. 배열 혹은 벡터로 구현한 heap은 다음과 같은 특성을 가집니다. 1) heap의 key 개수가 n이라면, 벡터의 크기는 n+1이다. 2) index i의 벡터 자리를 배정받은 node의 left child는 2i, right child는 2i + 1에 위치한다. 3) index 0번째는 실제로 사용되지 않는다(임시변수로 보통 활용함) 4) 마지막 node의 위치를 쉽게 알 수 있다 2021. 2. 27. [Heap]30. Heap-Sort(힙 정렬) 목차 1. Heap-Sort(힙 정렬) 2. 기존 PQ Sorting과 비교 1. Heap-Sort(힙 정렬) Heap을 활용한 sort은 다음과 같은 특징을 지닙니다. 1) 소요되는 메모리 양은 O(n) 2) insert, removeMin()은 O(logn)의 시간 소모 3) size, empty, min은 O(1)의 시간 소요 이때, insert과 removeMin에 O(logn)의 시간이 소모되므로, n개의 임의의 순서로 이루어져있는 배열을 정렬할 시, O(nlogn)의 시간만에 heap을 생성할 수 있습니다. 2. 기존 PQ Sorting과 비교 기존의 PQ Sorting을 사용할 시, Selection Sort 혹은 Insertion Sort은 Sorting에 O(n^2)의 시간이 소모되었습니.. 2021. 2. 27. [Heap]29. Insertion/Removal from a heap(힙에서의 삽입, 제거) 목차 1. Insertion into a heap(힙에서의 삽입) 2. Upheap 3. Removal from a heap(힙에서의 제거) 4. Downheap 5. Updating the last node(마지막 node 위치 업데이트) 1. Insertion into a heap(힙에서의 삽입) Heap에서 어떤 요소를 삽입하거나 삭제할 경우, heap이 가지는 특성인 1) 구조 맞추기, 2) 순서 맞추기, 이 2가지만 지키면 됩니다. 이중 구조는 일정하기 때문에, 우선 구조를 맞추고, 그 후에 순서를 맞추는 방식을 사용하게 됩니다. 따라서 heap에서 새로운 element를 삽입할 경우, 1) 해당 heap의 마지막 node를 찾고, 새로운 element가 들어갈 node의 위치를 확인한다. 2).. 2021. 2. 27. [Heap]28. Heap(힙) 목차 1. Heap(힙) 2. Height of a Heap(힙의 높이) 3. Heaps and Priority Queues(힙과 우선순위 큐) 1. Heap(힙) Heap(힙)은 특정한 규칙를 따르고 있는 binary tree입니다. 이 특정한 규칙은, 1) Heap-Order - 모든 internal node v에 대하여, 자식의 key값이 부모의 key값보다 항상 크거나 같아야 한다. - (단, root 제외) - key(v) >= key(parent(v)) 2) Complete Binary Tree - 이전에도 언급하였으나, heap은 complete binary tree를 따라야 한다. - 이는 모든 레벨의 node가 가득 차있어야 하며, 마지막 레벨의 node는 왼쪽으로 치우쳐있는 binary.. 2021. 2. 26. [Priority Queue]27. Priority Queue Sorting(우선순위 큐 정렬) 목차 1. Priority Queue Sorting(우선순위 큐 정렬) 2. Selection Sort 3. Insertion Sort 4. In-place Insertion Sort 1. Priority Queue Sorting(우선순위 큐 정렬) Priority Queue(우선순위 큐)가 중요한 내용을 먼저 꺼내는 ADT이니 만큼, PQ ADT는 들어온 데이터들을 key 값을 기준으로 정렬을 해야합니다. 이를 Priority Queue Sorting이라고 하며, 이를 구현할 수 있는 방법은 다양합니다. 2. Selection Sort Selection Sort(선택정렬)은 PQ-sort의 일종으로, 해당 priority queue가 정렬되지 않는 sequence와 연결되어 있는 구조를 뜻합니다. Se.. 2021. 2. 26. [Priority Queue]26. Priority Queue(우선순위 큐) 목차 1. Priority Queue ADT(우선순위 큐) 2. minPQ, maxPQ 1. Priority Queue ADT(우선순위 큐) 1) 특징 - Priority Queue ADT(우선순위 큐)는 queue의 성질을 따르지만, 필요한, 그리고 중요한 내용을 먼저 꺼내는 방식을 말합니다. 2) 주요 기능 - insert(e): e라는 element를 insert하는 함수 - removeMin(): 가장 작은 key를 지닌 값을 제거하는 함수 3) 부가 기능 - min(): 가장 작은 key를 지닌 값을 반환, 제거하지는 않는다 - size(), empty() 2. minPQ, maxPQ Priority Queue는 크게 2가지로 나뉘는데, minPQ와 maxPQ로 나뉘어집니다. 이름에서 추측할 수.. 2021. 2. 26. [Trees]25. Binary Trees Traversal(이진 트리 탐색) 목차 1. Inorder Traversal(중위 순회) 2. Print Arithmetic Expressions 3. Evaluate Arithmetic Expressions 2. Euler Tour Traversal(오일러 탐색) 1. Inorder Traversal(중위 순회) Inorder Traversal(중위 순회)는 해당 node가 external이 아니라면, 1) 왼쪽 자식의 node를 방문한 후 2) 현재 node를 print 3) 그 후 오른쪽 자식의 node를 방문함 위의 과정을 거치는 방법을 말합니다. 이는 실제로 이진 탐색 트리를 그리는 경우, 활용될 수 있습니다. - x(v) = inorder traversal 순위 - y(v) = node v의 높이 2. Print Arithme.. 2021. 2. 25. 이전 1 ··· 7 8 9 10 11 12 13 ··· 18 다음
