힙 정렬(heap sort)
힙 정렬 알아보기
힙 정렬은
힙의 특성을 이용하여 정렬하는 알고리즘이다.
힙은,
'부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는
완전 이진 트리이다.
이 때, 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다.
아무튼, 두 값의 대소 관계가 일정하면 된다.
? 힙(heap)은 쌓아놓음, 쌓아놓은 더미는 뜻이다. 힙 정렬이 어렵다면 9장을 먼저 읽어도 된다..
저는 하라면 하는 사람입니다
대충 읽어보고 오겠습니다
대충 알았습니다
완전 이진 트리는 자식 차수가 2인,
왼쪽 트리부터 순차적으로 채우는 트리이다.
힙에서는
부모와 자식 관계는 일정하지만,
형제 사이의 대소 관계는 일정하지 않다.
그래서 힙은 부분 순서 트리(partial ordered tree)라고도 한다.
가장 위쪽에 있는 루트를 a[0]에 저장하고,
레벨 1씩 내려가면서 왼쪽에서 오른쪽까지 따라간다.
이 과정에서 배열의 인덱스를 1씩 증가시키면서
각 원소를 저장한다.
이 작업을 가장 마지막에 있는 원소까지 반복하여 힙을 배열에 저장하여 완료한다.
이러한 순서로 힙을 배열에 저장하면,
부모 인덱스,
왼쪽 아래에 있는 자식 인덱스,
오른쪽 아래에 있는 자식 인덱스 사이에는
다음과 같은 관계가 성립한다.
원소 a[i]에서
- 부모: a[(i-1)//2]
- 왼쪽 자식 : a[i*2+1]
- 오른쪽 자식 : a[i *2 +2]
예를들어,
a[3]의 부모는 a[1]이고 왼쪽자식은 a[7], 오른쪽 자식은 a[8]이다.
힙 정렬의 특징
힙 정렬은
'힙에서 최댓값은 루트에 위치한다'라는 특징을 이용하여 정렬하는 알고리즘이다.
다음과 같은 작업을 반복한다.
- 힙에서 최댓값인 루트를 꺼낸다.
- 루트 이외의 부분을 힙으로 만든다.
이 과정에서 꺼낸 값을 나열하면,
정렬이 끝난 배열이 완성된다.
즉, 힙 정렬은 선택 정렬을 응용한 알고리즘이다.
(최소값을 앞으로 나열하는게 선택인데...
최대값들을 찾아서 앞에 나열한다는 거군.)
예를 들어, 힙 정렬에서
최댓값인 루트를 꺼낸 뒤,
다시 남은 원소 중에 최대값을 구한다.
남은 9개 원소로 구성한 트리도 힙이 되도록 재구성하는 것이다.
(근데 왜 굳이 이런 걸 쓴담?)
루트를 삭제한 힙의 재구성
루트를 삭제하고 힙을 다시 구성하는 순서를 보자.
(왜 그런 일을...하는데??)
(삭제 과정 예습?)
대강
- 루트가 없어진다.
- 마지막 원소를 루트 자리에 놓는다.
- 자식들과 비교해서 큰 값을 부모자식 체인지한다.
- 트리가 될 때까지 반복한다...
...
인 것 같다.
루트를 삭제하고, 다시 힙으로 만들기 위해
원소를 알맞은 위치로 이동하는 순서는 다음과 같다.
- 루트를 꺼낸다.
- 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
- 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래로 내려가는 작업을 반복한다. 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.
내가 위에서 한 말과 똑같군.
약간 다...
다르..
정의가 중요하니까 아래가 맞겠죠
힙 정렬 알고리즘 알아보기
오.
이걸 쓰는 이유는
일단 힙 정렬을 시키고 나면
맨 앞 루트의 값만 차례대로
맨 뒤로 보내버리면
오히려 정렬이 되어버리는 군
(10) 9 8 7 6 5
=>
(9) 8 7 6 5 (10)
=>
(8) 7 6 5 (9) (10)
...
쓰면서 깨달았는데 마냥 뒤가 아니라
역순으로 넣는 거구만(끝에서 추가가 아니라 끝에서 앞으로 한칸씩 이동하며 추가..)
이 값을 간단히 정리하면 다음과 같다.
여기서 n은 배열의 원소 수,
i는 배열의 마지막 인덱스이다.
- i를 n-1로 초기화한다.
- a[0]과 a[i]를 교환한다.
- a[0], a[1] ... a[i-1]을 힙으로 만든다.
- i를 1씩 감소시켜 0이 되면 종료한다. 그렇지 않으면 2로 돌아간다.
이 순서대로 힙 정렬을 수행한다.
이 때 중요한 것은,
배열의 처음 상태가 힙의 요구사항을 만족하지 않을 수 있으므로,
이 순서를 적용하기 전에 배열을 반드시 합으로 만들어야한다는 점이다.
엥
왜 3번 과정이 있는거지
아아아아
잘못 이해했군
힙 정렬이 그거구나
루트를 꺼내서 뒤에 보내서
결국 정렬 시키기는 하지만?
루트를 꺼내기 전에 있는 배열을 계속 힙을 유지하도록 정리한 다음에 이걸 해야하는 거고,
이 정렬 법 자체를 힙 정렬이라고 할뿐,
힙 상태로 만드는 정렬은 아니다!
라는 것이다.
배열을 힙으로 만들기는 다음에 나온다.
배열을 힙으로 만들기
엥
이것만 하면 힙이 끝이라고?
꿀이군
아무튼 루트를 삭제한 힙의 재구성을 공부한 이유를 알아냈다
구성을 정말 잘했다.
배열을 힙으로 만들 때는,
만약 서브트리가 힙이라면,
그 위에 오직 루트만 힙이 아닐 경우에는,
루트를 삭제한 힙의 재구성의 원리를 사용하여,
계속..그..
마지막 원소를 루트에 보냈을 때
힙을 유지시키기 위해 힙을 재구성하는 걸 반복하여
아래 서브트리부터 시작하여
맨 마지막 루트까지
점진적으로 힙으로 만드는 것이다.
이를 상향식(bottom-up)이라고 한다.
정확히는,
- 먼저 가장 아랫 부분의 오른쪽 서브 트리의 힙을 만든다.
- 같은 단계에 있는 왼쪽 서브 트리도 힙으로 만든다.
- 완료하면, 한 레벨 위로 이동하여 각각의 서브 트리를 힙으로 만든다...
그리고 무자비한 책은
바로 힙 정렬 알고리즘을 구현해버립니다
down_heap() 함수와
heap_sort() 함수다.
-
down_heap()
배열 a에서 a[left] ~ a[right] 원소를 힙으로 만든다.
a[left] 이 외에는 모두 힙 상태라고 가정하고,
a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다. -
heap_sort()
원소 수가 n인 배열 a를 힙 정렬하는 함수다.
다음과 같이 2단계로 구성된다.
- down_heap() 함수를 호출하여 배열 a를 힙으로 만든다.
- 최댓값인 루트 a[0]을 꺼내, 배열의 마지막 원소와 교환하고, 배열의 남은 부분을 다시 힙으로 만드는 과정을 반복하여 정렬을 수행한다.
아..
이걸...
맨 땅에 구현하라니.......
젠장.........................
- 부모: a[(i-1)//2]
- 왼쪽 자식 : a[i*2+1]
- 오른쪽 자식 : a[i *2 +2]
def heap_sort(a:MutableSequence) -> None:
def down_heap(a:MutableSequence,
left:int, right:int) -> None:
root = a[left]
a[left] = a[right]
if a[left] < a[left*2+2] and
a[left] < a[left*2+1] :
a[left], a[left*2+2] =
a[left*2+2], a[left]
elif a[left] < a[left*2+2] or
a[left] < a[left*2+1] :
a[left], a[left*2+1] =
a[left*2+1], a[left]
elif left = right:
break
else :
break
n = len(a)
for i in range((n-1)//2, -1, -1):
down_heap(a,0,n-1)
while n != 1:
root = a[0]
a[0], a[n-1] = a[n-1], a[0]
for j in range((n-2)//2,-1,-1):
down_heap(a[:n-1],0,n-2)
n -=1
이게 되네...
내 실력.....아니 맞는 코드인지도 모르지만
내 실력이 늘은건지
개소리 코드력이 늘은 건지
그냥 책이 너무 잘 써놔서 그런건지
잘 모르겠군...
가장 헷갈린건 for~ 에서 range설정으로...
나머지 모든.. 것을 힙정렬로 만드는 걸 반복한다..
라는 게..
아니 해야하는 건 알지만
남은 배열을 모두 힙으로 만들기 위해 몇번 반복해야하는가..이거 잘 모르겠단 말이지
정답 코드 보시겠습니다
def heap_sort(a:MutableSequence) -> None:
def down_heap(a:MutableSequence,
left:int, right:int) -> None:
temp = a[left]
parent = left
while parent < (right+1)//2:
cl = parent * 2 + 1
cr = cl + 1
child = cr if cr <= right
and a[cr] > a[cl] else cl
if temp >= a[child]
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
for i in range((n-1)//2,-1,-1):
down_heap(a, i, n-1)
for i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0]
down_heap(a,0,i-1)
cl : 차일드 레프트
cr : 차일드 라이트
child : 보통 라이트하겠지만
라이트가 레프트보다 크고, 라이트가 맨끝은 아닐때
레프트를 줄게요
대충
알았다
down_heap은
루트에 알맞지 않은 자리가 있을때
알맞은 자리를 찾을때까지
자식 노드와 비교하면서
끊임없이 내려가는 거고,
그래서 그 알맞지 않은 요소를 추적하기 위해
parent라는 인덱스를 쓰는 거고,
자식과 자리를 바꾸면
이제 자식의 인덱스 자리로 가는 거니까
parent= child 해준다.
그리고 이제 그거 다 내려갔다?
사실 여태 교환한게 아니라
자식 값이 더 커?
그럼 자식 값을 그 자리에 넣어.
라는 거 기때문에
맨처음의 그 루트에 알맞지않은 요소값은
어디에도 없으므로 임시로 저장해둔 temp에서 꺼내서
마지막으로 찾아낸 그 알맞은 인덱스에
temp를 넣어줌.
(n-1)//2가 범위인건
이진 트리라서 둘중 한 경로만 내려가기때문에
횟수가 전체 값의 절반이기때문이고,
그렇게
일단 힙 만듬.(0~ n-1), (1~ n-1) ...
맨 뒤에 보냄. (대신 맨 뒤 자리가 정렬할수록 바뀌니까, 전체 범위 n-1에서 0까지 역순으로 하나씩 넣음.)
다시 남은 걸로 힙 시킴.(다음에 보내기 전에, 남은 범위로 힙정렬을 함. i개를 보냈기때문에, 0부터 i-1까지의 값을 힙 화 시키면 됨.)
내가 한 건...
꾸준히 부모 노드에 있는건 맨 아래까지 보낸게 아니라, 한번만 함.
그래서 만약 배열이 늘어나면 재귀적인게 아니라,
바로 위의 부모와 자식은 되겠지만
맨 아래의 자식까지 힙이 유지되지 않았을 거임.
바꾼다는 건 알았는데, 맨 아래까지 보낸다는 로직 이해 부족.
두번째는
힙 정렬 자체는 배열 전체에서 시행하는거라서
범위가 틀렸고,
아마 나도 한번만 바꾼다는 사실을 알기 때문에
맨 아래까지 보내려면 저걸 처음부터 끝까지 반복하면 되나? 라는 생각이었는데.
앞 같은 이유로 안 되기때문에...
그래서 while과 for로 뺐는데,
down_heap 자체가 전부 힙 화 시킨다는게
좀 어려웠는듯!
끝!
힙 정렬의 시간 복잡도
힙 정렬은 선택 정렬의 응용인데,
선택 정렬은 늘 찾아야하고,
힙 정렬은 바로 뽑으면 되지만 계속 힙으로 재구성해야한다.
그렇지만
단순 선택 정렬에서 최댓값인 원소를 선택하는 시간 복잡도는 O(n)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다.
따라서 단순 선택 정렬의 시간 복잡도는 O(n**2) 지만,
힙정렬은 원소의 개수만큼 작업을 반복하므로
전체 정렬하는데 걸리는 시간 복잡도는 O(nlong n)으로 크게 줄어든다.
? heapq 모듈을 사용하는 힙 정렬
heapq 모듈은
원소를 추가하는 heappush() 함수와
힙에서 원소를 제거하는 heappop() 함수를 제공한다.
이때 푸시와 팝은 힙의 조건을 유지하며 수행된다.
그래서 이렇게 하면 구현된다.
heap = []
for i in a:
heapq.heappush(heap, i)
for i in range(len(a)):
a[i] = heapq.heappop(heap)
전부 힙으로 재구성시킴
재구성 시킨걸 다 꺼내서 0부터 채워버림
오.
끝!
