Accelerated Heapsort

가속 힙정렬은 기존의 힙정렬보다 2배정도 빠른 속도를 보장한다.
가속 힙정렬은 힙정렬과 유사하지만 힙정렬은 deleteMax를 작업하는데 2nlogn + n의 시간이 걸리는 반면 가속 힙정렬은 nlogn + nloglog의 복잡도를 갖는다.

구현 방법: 바이너리 서치의 방법을 응용하고있다 일단 트리의 절반까지 내려온뒤 위로 올라갈지 아래로 내려갈지 생각하는 기법이다. 주요 함수는 promote, bubbleupheap등으로 나뉜다.
일단 deleteMax를 진행하면 루트의 값이 가장 아래에 오른쪽에 있는값으로 수정된다. 해당 값이 들어갈 적절한 위치를 찾아주기 위해 일단 트리의 절반까지 내려온다. 절반까지 내려온뒤 부모의 키가 자신보다 작다면 부모의 키가 자신보다 클때까지 올라간다. 만약 부모의 키가 자신보다 크다면 위 과정을 재귀적으로 반복한다.

위 알고리즘은 sort함수중에서 nlogn의 복잡도를 가지므로 optimal하다고 볼 수 있다