[작성중] 힙

힙 정렬의 수행시간은 O(nlogN) 이다. 수행시간은 병합정렬과 비슷하고 삽입정렬과는 내부 정렬이라는 점이 같다. 따라서 상수 개의 원소를 초과해서 배열 밖에 저장하는 일은 없다.
힙 정렬은 상기의 두 정렬의 장점을 혼합한 것이다.
(이진) 힙 자료구조는 완전 이진트리로 볼 수 있는 배열 객체 이다. 트리의 각 노드는 배열에서 한 원소와 대응된다.

이 트리는 가장 낮은 레벨을 빼고는 완전히 차 있고, 가장 낮은 레벨은 왼쪽부터 채운다. 힙을 나타내는 배열 A는 두개의 자식 노드를 갖는다.
노드의 인덱스 i가 주어지면 부모Parent(i), 왼쪽 자식Left(i), 오른쪽 자식Right(i)는 아래와 같이 구할 수 있다.

Parent(i)
| return i/2
Left(i)
| return 2i
Rignt(i)
return 2i+1

컴퓨터에서 Left 프로시저는 i의 이진 표현을 왼쪽으로 한 비트 시프트하고 Right는 왼쪽으로 한 비트 시프트 한 뒤 1을 더해 빠르게 계산한다고 한다. Parent의 경우 오른쪽으로 한 비트 시프트 한다.

최대힙과 최소힙

최대힙은 아래와 같은 특성이 성립한다.
A[Parent(i)] >= A[i]
다시 말해 부모 노드는 노드의 값보다 크다. 루트 노드가 최댓값
최소힙은 그 반대다.
A[Parent(i)] <= A[i]
즉, 최소힙의 최솟값은 루트에 있다.