힙 정렬은 힙이라는 특수한 자료구조 그 중에서도 이진완전트리를 사용한다.

힙에는 2가지 종류가 있는데 하나는 최대힙과 최소힙이다. 이는 값의 방향성의 차이지 큰 차이는 없다.

최대힙 : 부모 노드가 자식 노드보다 큰 값을 가지는 힙

최소힙 : 부모 노드가 자식 노드보다 작은 값을 가지는 힙

1. 힙 만들기

열심히 그렸다.
배열을 노드로 만드는것은 위 사진과 같다.

가장 위의 노드를 1로 뒀을 때 자식 노드는 좌측은 i 2의 인덱스 값을 가지고 우측은 i 2 + 1라는 인덱스 값을 가진다.

그리고 그 노드의 부모 노드는 i / 2의 인덱스 값을 가진다.

def parent(alist, node):
	return alist[index // 2]
    
def left(alist, node):
	return alist[index * 2]
    
def right(alist, node):
	return alist[(index * 2) + 1]

부모, 자식 노드들의 값을 반환해주는 코드

힙을 만드는 과정은 간단하다.

1. 배열을 힙으로 만든다.

2. 만들어진 힙을 규칙에 맞게 정렬한다.

아래는 힙 정렬을 하는 함수이다.

기준은 최소힙이다.

def heapify(alist):#힙정렬
	for i in range(1, len(alist) + 1):
		node = alist[i]
        
        leftI = left(i)
        if(len(alist) > leftI):#값이 넘어가서 넘치는거 방지
        	if(node > alist[leftI]):#최소힙이기 떄문에 자식 노드가 값이 작으면
            	alist[i], alist[leftI] = alist[leftI], alist[i]#스왑
                
        rifgtI = right(i)
        if(len(alist) > rifgtI):#우측
        	if(node > alist[rifgtI]):
            	alist[i], alist[rifgtI] = alist[rifgtI], alist[i]

위와같은 과정으로 조정이 가능하다.

이를 그림으로 표현하면

열심히 그렸다.
위와같은 배열을 처음에 힙으로 만든 후 정렬의 과정을 거친다.

수행시간은 O(nlog(n))이다.