힙6 [Heap]33. Bottom-up Heap Construction 목차 1. Merging Two Heaps 2. Bottom-up Heap Construction 1. Merging Two Heaps Heap-sort도 충분히 빠른 수행이 가능한 강력한 방법이지만, heap을 구성하는 시간을 총 O(n)으로 단축할 수 있는 방법이 있습니다. 이는 두개의 node와 하나의 key값이 주어졌을 때, 이를 서로 합치는 Merging Two Heaps를 활용하여 해결할 수 있습니다. 순서는 1) 두개의 heap과 1개의 key값을 준비함 2) 1개의 key값을 root로 하고, 나머지 두개의 heap이 subtree가 되는 새로운 node를 만든다 3) root에서 downheap실행, heap의 규칙을 성립시킨다 2. Bottom-up Heap Construction Bo.. 2021. 2. 28. [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. 이전 1 다음
