알고리즘 [힙정렬]

🔎 배열에 기초한 힙 구현

물론 연결리스트로도 구현 가능하다.

n개의 키를 가진 힙의 크기 n의 배열을 사용하여 표현가능

특징

• 이때, 첨자 i에 존재하는 노드에 대해 왼쪽 자식은 2i에 오른쪽 자식은 2i+1에 존재한다.
• 같은 맥락으로 부모는 i/2에 존재
• 연결리스트 구현이 아니기 때문에 링크를 명시적으로 저장할 필요가 없다.
• 외부노드를 표현할 필요가 없다.
• 첨자 0셀을 사용하지 않음
• 마지막 노드의 첨자: 항상 n (즉 insertitem작업은 첨자 n + 1위치에 삽입하는 것에 해당 / removeMin은 첨자 n에 위치에서 삭제하는 것)

🔎 힙 정렬

특징

• 공간 사용량은 O(n)
• insertitem, removeMin은 O(log n)
• size, isEmpty, minkey, minElement는 O(1)시간에 수행
• 정렬 시간이 O(n log n)시간이 걸림
• 앞 서 배운 선택정렬, 삽입정렬보다 훨씬 빠르다..

Alg heapSort(L)
    input list L
    output sorted list L

1. H <- empty heap
2. while(!L.isEmpty())
    k <- L.removeFirst()
    H.insertItem(k)
3, while(!H.isEmpty())
    k <- H.removeMin()
    L.addLast(k)
4. return

제자리 정렬 아님

위와 같은 의사코드로 이루어 지는 정렬을 힙 정렬이라고 한다.

여기서! 제자리 힙 정렬은 공간 사용을 줄이고
상향식 힙 생성은 속도를 높힌다.

정리하자면 상향식 힙 생성으로 힙을 생성하고 힙 정렬은 제자리 힙정렬을 사용하여 공간 사용을 줄인다.

제자리 힙 정렬

제자리 힙 정렬은 정렬되어야 할 리스트가 배열로 주어진 경우에 적용가능, 최대힙으로 구성

Alg inplaceHeapSort(A)
    input array A of n keys
    output sorted array A

1. buildHeap(A)
2. for i <- n downto 2
    A[1] <-> A[i]
    downHeap(1,i-1)
3. return

Alg buildHeap(A)
    input array A of n keys
    output heap A of size n

1. for i <- 1 to n
    insertItem(A[i])
2. return

Alg downHeap(i, last)
    input index i of array A representing a
    maxheap of size last
    output none

1. left <- 2i
2. right <- 2i + 1
3. if(left > last)
    return
4. greater <- left
5. if(left <= last)
    if(key(A[right]) > key(A[greater]))
        greater <- right
6. if(key(A[i]) >= key(A[greater]))
    return
7. A[i] <-> A[greater]
8. downHeap(greater, last)

힙 정렬은 입력된 배열을 힙으로 만드는데 이 과정을 거치고 난 뒤 위에서 부터 하나씩 뽑아낸다.

maxheap의 성격을 계속 유지한 채 루트값을 다시 저장하는 것..

-> -> 이 방향으로 힙을 만들고 <-<- 다시 이방향으로 리스트를 뽑는다.

maxheap으로 만든 이유도 루트값을 뽑고 난뒤 맨뒤부터 삽입하면 결국 오름차순 정렬이 만들어 진다.

상향식 힙 생성

Alg buildHeap(L)
    input list L sorting n keys
    output heap T storing the keys in L

1. T <- convertToCompleteBinaryTree(L)
2. rBuildHeap(T.root())
3. return T

Alg rBuildHeap(v)
    input node v
    output a heap with root v

1. if(isinternal(v))
    rBuildHeap(leftChild(v))
    rBuildHeap(rightChild(v))
    downHeap(v)
2. return

convertToCompleteBinaryTree 는 리스트 L을 완전 이진트리 T로 전환한다.

상향식 힙 생성은 두개의 힙을 합병하여 힙을 생성한다.