[heap sort] 힙 힙 힙!

Heap tree

---

parent 와 child로 이루어진 구조

 

heapify: 트리를 heap 트리로 바꾸는 과정

siftdown: (max) heap에서는 parent가 child보다 크면 된다

1단계만 실제로 보자면 root(6)의 right child(4)에서는 child와 비교헀을때, 8이 가장 크기 때문에 8과 4를 swap해준다.

  

이러한 과정을 거치면 아래와 같이 된다.

[6, 2, 4, 9, 7, 5, 8]

[6, 2, 8, 0, 7, 5, 4]

[6, 9, 8, 2, 7, 5, 4]

[9, 7, 7, 2, 6, 5, 4]

(max) heap에서는 가장 큰 값만 뽑으면 되기 때문에, 8, 5, 4의 경우 더이상 순회 하지 않는다.

 

def heapsort(a):
    def swap(a, i, j):
        tmp = a[i]
        a[i] = a[j]
        a[j] = tmp

    def siftdown(a, i, size):
        l = 2*i+1
        r = 2*i+2
        largest = i
        if l <= size-1 and a[l] > a[i]:
            largest = l
        if r <= size-1 and a[r] >a[largest]:
            largest = r
        if largest != i:
            swap(a, i, largest)
            siftdown(a, largest, size)

    def heapify(a, size):
        p = (size//2) - 1
        while p>=0:
            siftdown(a, p, size)
            p -= 1

    size = len(a)
    heapify(a, size)

    # heap sort 과정
    end = size-1
    while(end>0):
        # 0과 마지막 node와 바꿔줌
        swap(a,0, end)
        # swap이 된 마지막 node는 배제하고 siftdown
        siftdown(a, 0, end)
        end -=1​