참고
파이썬 알고리즘 git repo

ratsgo 님의 힙 정렬
안경잡이 개발자님의 힙 정렬

힙을 들어가기 전에

트리

• 트리 구조는 가지가 뻗어나가는 것처럼 데이터가 서로 연결된 구조를 말한다.
• 트리는 계층 모델이다
• full node는 왼쪽, 오른쪽 자식 노드가 모두 존재하는 노드를 칭한다.

이진 트리

컴퓨터 안에서 데이터를 표현할 때, 데이터를 노드에 담은 뒤 노드를 두 개씩 이어붙이는 구조를 말한다. 부모노드에서 자식 노드로 가지가 뻗히게 된다. 모든 노드의 자식 노드가 2개 이하이다. (0개, 1개 또는 2개)

완전 이진트리

노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리다. 위는 완전이진트리이고, 밑은 아니다

힙

최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리다. 힙에는 최대 힙과 최소 힙이 존재하는데, 최대 힙은 부모 노드가 자식 노드보다 큰 힙이다.

힙정렬을 하기 위해서는 데이터를 힙 구조가 되도록 만들어야 한다.

힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

최대힙: 부모노드가 자식노드보다 큰 트리
특정 노드를 기준으로 위쪽으로 올라가는 상향식 구현 방식과, 아래로 내려가는 하향식 구현 방식이 있고 시간 복잡도는 동일하다.

힙 생성 알고리즘

힙 정렬을 수행하기 위해 사용하는 알고리즘. 하나의 노드에 대해서 수행하게 된다. 하나의 노드를 제외하고는 힙이 구성되어 있는 상태를 가정한다.

• 특정 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘
• 자식 노드로 내려갈 때마다 노드의 개수가 최대 2배씩 증가한다는 점에서 O(logN)의 시간복잡도를 가진다.

장점

병합 정렬과 다르게 추가적인 배열이 필요하지 않아, 메모리 측면에서 효율 적이다. 항상 시간복잡도를 O(logN)이하로 보장할 수 있다는 점에서 강력하다. 이론적으로는 퀵 정렬, 병합 정렬보다 우위에 있지만 속도로만 비교했을 때는 퀵 정렬이 평균적으로 빠르기 때문에 힙 정렬이 일반적으로 많이 사용되지는 않는다.