[파이썬 자료구조] Binary Heap Binary Heap 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 예제는 모두 최소힙인 경우임 먼저 이진힙에서 최소값을 삭제하는 예를 ohaengsa.tistory.com 힙정렬 힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다....라고 위키에 써져있음 간단히 살펴보자 1단계. 5가 삽입된 경우임. 트리의 맨 아래에서 왼쪽에다가 붙혀줌 2단계. 위를 쳐다보니 40이 있다. 5가 더 작으니까 40과 교환한다. 3단계. 위를 쳐다보니 이제 20이 있다. 5가 더작으니까 교환한다...

Binary Heap 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 예제는 모두 최소힙인 경우임 먼저 이진힙에서 최소값을 삭제하는 예를 살펴보자 1단계. 2를 삭제하면 트리가 파괴되기 때문에 last노드인 7을 2와 바꾼다. 그리고 2를 삭제 2단계. 트리에서 7이 가장 작은 값이 아니므로 7의 아래 레벨인 5와 6 중에서 작은 값을 7과 교환함 수행시간은 last노드를 찾는데 걸리는 시간뿐 즉, 트리의 높이만큼의 시간이 걸림> O(logn) n이 노드의 개수일 때 트리의 높이는 log(n)이라는것을 기억하자 다음은 삽입하는 예를 살펴보자 1단계. 노드1을 노드6의 왼쪽에 삽입함 2단계. 노드1에서 위를 쳐다보니 노드2와 노드6이 있음 1..