Algorithm14 [자료구조] 힙(Heap) - 2. 파이썬 구현 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙과 배열 일반적으로 힙 구현시 배열 자료구조를 활용한다. 주의할 점은 배열은 인덱스가 0부터지만, 힙 구현의 편의를 위해 root의 인덱스를 1로 지정한다. 부모 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2 + 1 📌 힙에서 데이터 삽입 구현 (Max Heap) ✔️ move_up, insert 구현 class Heap: def __init__(self, data): # 배열로 힙을 구현 self.heap_array = list() # heap_array[0]은 사용.. 2021. 6. 25. [자료구조] 힙(heap) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙 (Heap) 이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)이다. 여기서 완전 이진 트리는 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 따라서 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 📌힙을 사용하는 이유 배열에 데이터를 넣고 최대값/ 최소값을 찾으려면 O(n)이 걸린다. 하지만 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다. ✔️ 이처럼 최대값 또는 최소값을 빨리 찾아야 하는 자료구조 및 알고리즘 구현에 활용된다. 📈 시간 복잡도 배열에 데이.. 2021. 6. 25. 이전 1 2 3 4 다음
