(힙분류) 힙정렬

힙 정렬은 힙 자료구조를 이용하여 자료를 정렬한다.

우선은 힙 자료구조를 본다면 완전 이진트리이면서 동시에 최대 트리 호은 최소 트리를 말하는 것으로,

최대 힙은 루트노드의 키가 트리 전체 중 항상 최대값을 지니고 최소 힙은 루트 노드가 전체 중 항상 최솟값을 가지는 특성이 있다.

힙은 우선 순위 대기열에 사용하기에 매우 효율적이다. 

또한 힙이라는 자료구조 자체에서도 정렬 기능이 있다..왼쪽 자식은 루트보다 작고 오른쪽은 크다

(틀렸다. 하나의 노드는 그 노드의 모든 자손(왼, 오른쪽)보다 큰 키 값을 가진다. 루트에는 항상 가장 큰 키 값을 갖는 노드가 위치한다)

(최소힙은 최대를 최소로만 바꿔서 읽으면 됨..)

(그럼 위의 조건은 어떤 자료구조인가? 바로 이진 검색 트리의 조건이다.)

힙의 삽입 삭제 알고리즘은 모두  O(logn)이다.

단점은 공간이 두배로 늘어난다.. 왜냐면 정렬되지않은것과 힙으로 자료구조 정렬된 것..2개로 구분되는데..

1) 열혈강의 자료구조에서는 배열에 있는 데이터를 힙 자료구조에 맞게 이진트리에 삽입 후

(이진트리의 마지막 위치에 자료를 추가하고 부모 노드의 키 값과 비교하면서 이동한다) 삭제를 통해서 오름차순으로 정렬한다. (최소힙을 만들고

하는것이다..)

(일반적인 힙에서는 최상위 항목을 삭제할떄에는 삭제된 항목은 버리고, 힙을 다시 유효하게 정렬해야하니까 마지막 항목을 루트에 넣고 따라내려가기

알고리즘을 적용한다, 그러나 힙정렬에서는 정렬된 배열을 다시 만들어야 하므로..마지막 항목과 바꾸고 연결을 끊으면 된다..

삭제되는건 마지막 항목과 연결된다면...정렬된 데이터가..)

2) 게임프로그래머를 위한 자료구조에서는 아래처럼 한다.

여기서 그냥 정렬되지 않은 배열 자체를 힙으로 변환된다면..2개로 구분된게 1개로 될 수 있다.

힙으로 변경하는 알고리즘은

1. 힙의 밑에서 두 번째 수준의 가장 큰 값에 해당하는 색인을 찾는다.

2. 그 색인에 대해 WalkDown함수를 호출한다.

3. 그 색인을 1감소시킨다.

4. 그 색인이 0이 될 때까지 2와 3을 반복한다.

히프정렬의 특성은....평균 효율성은 O(nlogn) 이다....최선 평균 최악.. 정렬의 안정성은 유지되지 못한다.