[정렬] heap sort

완전이진트리(complete binary tree)

말단 노드를 제외한 모든 노드가 두 개의 자식 노드를 가지고 있는 이진 트리.

 

힙(heap)

완전이진트리에서, 모든 노드에 대해서 부모 노드의 값이 자식 노드의 값보다

크거나 같으면 Max heap,

작거나 같으면 Min heap이라 한다.

 

heapify(힙 생성)

1. 루트 노드(A)부터 모든 노드를 순회하며,

2. A와 A의 자식 노드를 비교하여, 교환하거나 그대로 둔다.

3. 2를 반복한다.

heapify는 하나의 노드에 대해 수행되는 과정을 반복하며,

해당하는 노드를 제외하고는 최대 힙이 구성되어 있는 상태라고 가정한다.

즉, 위에서부터 차례차례 서브 트리를 Max heap으로 만들어나가는 것이다.

 

insert(삽입)

1. 마지막 자리에 추가할 노드(A)를 삽입한다.

2. A와 A의 부모 노드를 비교하여, 교환하거나 그대로 둔다.

3. 2를 반복한다.

 

remove(삭제)

1. 루트 노드를 제거한다.

2. 루트 노드 자리에 마지막 노드(A)를 삽입한다. // 마지막 노드가 아닌 다른 노드를 택하면 트리의 중간이 비게 된다.

3. A와 A의 자식 노드를 비교하여, 교환하거나 그대로 둔다.

4. 3을 반복한다.

 

def heapify(heap):
    for i in range(1, n):
        child = i
        parent = (child-1)//2
        while child != 0:
            if heap[child] > heap[parent]:
                temp = heap[child]
                heap[child] = heap[parent]
                heap[parent] = temp
            child = parent
            parent = (child-1)//2


def insert(heap, x):
    heap.append(x)
    i = len(heap) - 1
    parent = (i-1)//2
    while (i != 0):
        if heap[i] > heap[parent]:
            temp = heap[i]
            heap[i] = heap[parent]
            heap[parent] = temp
        i = parent
        parent = (i-1)//2

def remove(heap):
    heap[0] = heap[len(heap) - 1]
    heap.pop()

    parent = 0
    leftChild = 1
    rightChild = 2

    while leftChild < len(heap):
        flag = 3 # left(1) or right(2) or stop(0)
        if rightChild < len(heap): # both child exist
            if heap[leftChild] >= heap[rightChild]:
                if heap[parent] < heap[leftChild]:
                    flag = 1
            else:
                if heap[parent] < heap[rightChild]:
                    flag = 2
        else: # only left child exists
            if heap[parent] < heap[leftChild]:
                flag = 1
        
        if flag == 1:
            temp = heap[leftChild]
            heap[leftChild] = heap[parent]
            heap[parent] = temp
            parent = leftChild
            leftChild = parent * 2 + 1
            rightChild = parent * 2 + 2
        elif flag == 2:
            temp = heap[rightChild]
            heap[rightChild] = heap[parent]
            heap[parent] = temp
            parent = rightChild
            leftChild = parent * 2 + 1
            rightChild = parent * 2 + 2
        elif flag == 3:
            break

def heap_sort(heap, n):
    for i in range(n-1, -1, -1):
    	# 루트 노드와 마지막 노드를 바꾼다.
        heap[0], heap[i] = heap[i], heap[0]

        root = 0
        child = 1

        while child < i:
            child = root * 2 + 1 # child는 기본적으로 leftChild이다.

            if child < i-1 and heap[child] < heap[child+1]:
            # leftChild, rightChild가 모두 존재하고, rightChild가 더 클 때
                child += 1 # 루트 노드와 바꿀 child는 rightChild가 된다.
            
            if child < i and heap[root] < heap[child]:
            # 여기서 child는 leftChild이다.
            # 루트 노드가 leftChild보다 작을 때
                heap[child], heap[root] = heap[root], heap[child]
                # 루트 노드와 자식 노드를 바꾼다.
            
            root = child



##### TEST #####
n = 12
heap = [8, 7, 3, 11, 5, 4, 12, 10, 9, 6, 1, 2]

### heapify
heapify(heap)
print(heap) # [12, 10, 11, 9, 6, 3, 4, 7, 8, 5, 1, 2]

### insert
insert(heap, 13)
print(heap) # [13, 10, 12, 9, 6, 11, 4, 7, 8, 5, 1, 2, 3]
insert(heap, 6.5)
print(heap) # [13, 10, 12, 9, 6, 11, 6.5, 7, 8, 5, 1, 2, 3, 4]

### remove
remove(heap)
print(heap) # [12, 10, 11, 9, 6, 4, 6.5, 7, 8, 5, 1, 2, 3]
remove(heap)
print(heap) # [11, 10, 6.5, 9, 6, 4, 3, 7, 8, 5, 1, 2]

### sort
heap_sort(heap, len(heap))
print(heap) # [1, 2, 3, 4, 5, 6, 6.5, 7, 8, 9, 10, 11]