힙2 python heapq heapq 모듈은 최소 힙(min heap)을 구현하는 데 사용되며, 최소 힙은 가장 작은 요소가 루트에 위치함을 보장한다. 그러나 다른 요소들 사이의 상대적인 순서는 보장되지 않는다. heapq의 각 원소의 인덱스를 k라고 할 때, k의 자식 원소들은 이진 트리 상의 특정 노드의 자식이 되므로 2k+1, 2k+2의 인덱스를 갖는다. heapq는 부모 노드가 항상 자식 노드보다 그 값이 같거나 작다는 특징을 갖는다. import 방법 import heapq 사용 heapq.heapify heapq.heapify 함수는 기존의 자료구조를 힙으로 변환하는 함수다. 이 함수는 파라미터로 전달된 리스트의 원소들을 재배치하여 힙의 조건을 만족하도록 한다. import heapq print() nums = [-5,.. 2023. 6. 1. Top down Approach 하향식(Top-Down) 방식은 노드가 ✔ ↓ 의 방향으로 먼저 간 다음, ✔ → 의 방향으로 채워진다. 이 두 순서로 노드가 채워지게 된다. 즉 위에서부터 채워나가되, 각 레벨에서의 삽입은 왼쪽에서 오른쪽 순서로 하게 된다. 이러기 위해선 두 가지 조건이 필요하다. 1. 각 노드에 저장된 값이 두 자식 노드에 저장된 값보다 크거나 같아야 한다. 작거나 같다는 조건으로 바꿔도 된다. 크기가 자식 노드보다 크거나 같은 경우를 Max heap이라 하고, 작거나 같은 경우를 Min heap이라고 한다. 2. 트리는 완전 균형 상태여야 하고, 마지막 레벨에 있는 leaf 노드들은 모두 트리의 가장 왼쪽 부분부터 채워져야 한다. 따라서 트리의 높이는 O(log n)이 된다. 이 두 조건은 자료구조 '힙'의 성질이.. 2017. 4. 20. 이전 1 다음