힙 정렬 heap sort

최악의 경우 시간 복잡도 O(nlogn), 추가 배열이 불필요(메모리 사용이 준다), 이진 힙 자료구조 사용

힙의 정의

complete binary tree이면서 heap property를 만족해야한다.

완전 이진 트리는 리프 노드를 제외한 모든 노드의 자식이 최대 2개인 노드이다.

왼쪽부터 차례로 노드를 채우는데 중간에 비어있는 노드가 있으면 안된다.

max heap property는 부모 노드가 자식 노드보다 크거나 같은 것이다.

min heap property는 부모 노드가 자식 노드보다 작거나 같은 것이다.

힙의 높이는 logn이다. n이 8이면 높이는 3이다. 왼쪽부터 채우면서 노드의 자식이 최대 2개이기 때문이다.

힙은 일차원 배열로 표현 가능 : A[1...n]

A[1]은 루트 노드

A[i]의 부모 = A[i/2]

A[i]의 왼쪽 자식 = A[i*2]

A[i]의 오른쪽 자식 = A[2*i+1]

힙의 특성 때문에 가능하다.

전체를 힙으로 만들기 max-heapify

1. 트리의 전체 모양은 complete binary tree

2. 왼쪽 서브트리는 heap, 오른쪽 서브트리도 heap, 루트 노드만 heap property를 만족하지 않음.

두 자식 노드 중 더 큰 노드와 부모 노드를 바꾼다.

max_heapify(A,i):

  if there is no child of A[i] //자식이 없다면 종료

    return;

  k = index of the biggest child of i; //자식 중 큰 값이 k

  if A[i] >= A[k] // 부모가 자식보다 크면 종료

    return;

  A[i],A[k]=A[k],A[i] //자식이 부모보다 크면 바꿈

  max_heapify(A,k);

배열을 힙으로 만들기

아래 레벨에서부터 올라오면서 자식이 있는 첫번째 노드를 max heapify한다.

build_max_heap(A)

  heap_size[A] = length[A]

  for i in range(length(A)//2,1,-1) //첫번째 부모 노드는 마지막 노드의 인덱스//2이다

    max_heapify(A,i)

시간 복잡도는 O(n)이다. 그러나 전체 시간 복잡도는 O(nlogn)이다.

정리

1. 리스트를 최대 힙으로 만든다.

2. 힙에서 최대값(루트)를 가장 마지막 값과 바꾼다.

3. 힙의 크기가 1 줄었다고 생각한다.

4. 루트 노드에 대해 heapify(1)한다.

5. 2~4번 반복한다.

heapsort(A)

  build_max_heap(A)               //O(n)

  for i in range(len(A)//2,2,-1)    //n-1 번 반복

    A[1],A[i]=A[i],A[1]               //O(1)

    heap_size -=1                   //O(1)

    max_heapify(A,1)               //O(logn)

총 시간 복잡도 O(nlogn)

arr=[2,8,6,1,10,15,3,12,11]
def downheap(cur, k): #현재 부모의 인덱스, 리스트의 길이
    while cur<k: 
        left=cur*2+1
        right=cur*2+2
        if left>=k and right>=k:break
        p=cur
        if left<k and arr[p]<arr[left]:p=left
        if right<k and arr[p]<arr[right]:p=right
        if p==cur:break
        arr[cur],arr[p]=arr[p],arr[cur]
        cur=p
def heapify(n):
    for i in range((n-1)//2,-1,-1): #첫 부모부터 루트까지
        downheap(i,n)
def heap():
    heapify(len(arr)) #배열을 힙화 한다.
    for k in range(len(arr)-1,0,-1):
        arr[0],arr[k]=arr[k],arr[0]
        downheap(0,k)
heap()
print(arr)