힙

[알고리즘] 힙 정렬

아래 글은 'Do it! 자료구조와 함께 배우는 알고리즘 입문(파이썬 편)'을 보고 정리한 것이다. 힙(Heap) 힙이란, 아래의 조건을 만족하는 완전 이진 트리이다. 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 형제의 대소 관계가 정해져있지 않으므로 부분 순서 트리(partial ordered tree)라고도 한다. 부모의 값이 자식의 값보다 항상 크다/작다. 인덱스 i에 대해 부모와 자식 인덱스 사이에는 다음과 같은 관계가 성립한다. 부모: a[(i-1)//2] 자신: a[i] 왼쪽 자식: a[i*2 + 1] 오른쪽 자식: a[i*2+2] 힙 정렬(Heap Sort) 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙에서 최댓값은 root에 위치한..