본문 바로가기

> 자료구조 구현16

최소 힙(min heap)의 구조를 가지고 있는 우선순위 큐 구현 import heapq queue = [] heapq.heappush(queue, [2, 'A']) heapq.heappush(queue, [5, 'B']) heapq.heappush(queue, [1, 'C']) heapq.heappush(queue, [7, 'D']) print(queue) """ [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']] """ for x in range(len(queue)): print(heapq.heappop(queue)) """ [1, 'C'] [2, 'A'] [5, 'B'] [7, 'D'] """ - 출처 : FASTCAMPUS 2020. 10. 10.
힙(heap)의 기본 구현 * 배열을 사용하여 힙을 구현한다. - 구현시, root node index는 1로 설정한다 - parent node's index = child node's index // 2 - left child node's index = parent node's index * 2 - right child node's index = parent node's index * 2 + 1 class Heap: def __init__(self, data): self.heap_array = list() self.heap_array.append(None) self.heap_array.append(data) def move_up(self, inserted_idx): if inserted_idx + \ self.heap_array.. 2020. 10. 10.
힙(heap)의 기본 * 힙(heap): 이진 트리의 일종으로, 최댓값 또는 최솟값을 빠르게 찾기 위해 고안되었다 완전 이진 트리의 성격을 가진다 * 완전 이진 트리(complete binary tree): 자식 노드를 삽입할 때 가장 왼쪽의 노드부터 삽입하는 트리 * 시간 복잡도: 힙에 데이터를 넣고, 최댓값 또는 최솟값을 찾으면, O(log n)의 시간 복잡도를 가짐 * 힙 구조의 유형: 최대 힙(Max Heap), 최소 힙(Min Heap) * 힙과 이진 탐색 트리의 비교 - 힙은 최대/최솟값에 초점을 맞추어 이를 빠르게 구하기 위한 구조 - 이진 탐색 트리는 탐색을 빠르게 하기 위한 구조 - 이미지 출처: www.fun-coding.org/Chapter11-heap.html - 내용 출처 : FASTCAMPUS 2020. 10. 10.
트리(tree) 기본 구현 * 객체지향 프로그래밍으로 트리를 구현함 class Node: def __init__(self, value): self.value = value self.left = None self.right = None class NodeMgmt: def __init__(self, head): self.head = head def insert(self, value): self.current_node = self.head while True: if value < self.current_node.value: if self.current_node.left != None: self.current_node = self.current_node.left else: self.current_node.left = Node(value).. 2020. 10. 8.

티스토리툴바