[자료구조] 힙 정렬(heap sort)

🔅힙 정렬(heap sort) 모양

힙 정렬은 크기를 기준으로 정렬된 시퀀스를 사용할 때 유용한 자료구조

마지막 레벨을 제외하고는 완전 이진트리의 구조를 가진다.(마지막 레벨 빼고 한 노드가 두개 이상의 자식 노드를 가진다)

• 최대 힙 : 부모 노드가 항상 자식 노드보다 큰 경우
• 최소 힙 : 부모 노드가 항상 자식 노드보다 작은 경우

원소간 대소관계는 부모 자식관계에만 있다. 형제 사이에서는 대소관계가 없다.

 

여기서 완전 이진트리와 다른 점은 이진트리는 값과 상관없이 정렬된다. 이진 트리는 부모노드와 자식노드 간 대소관계가 없다.

 

이진트리의 구조를 가진다는 말은, 인덱싱이 동일하다는 뜻.(부모 노드를 n이라고 할 때, 왼쪽 자식 노드는 2n, 오른쪽 자식 노드는 2n+1)

(그림을 보고 "배열로 나타낸다"는 말은 인덱스간 규칙이 있으나 찾아서 구현할 것이라는 말. -> 이진트리에서 배열로 나타내는 방법은 인덱스 n, 2n, 2n+1!!)

 

🔅힙 정렬(heap sort) 삽입,삭제

"가장 높은(혹은 낮은) 우선순위를 가지는 노드는 항상 뿌리 원소에 있다." => 시간복잡도 삽입,삭제 모두 O(log n)

원소의 삽입,삭제가 일어날 떄 전체 원소의 반만 보기 때문

 

**최대힙 기준

자식 노드로 들어간 22가 부모노드 10보다 크므로 옮겨준다

22와 10간 힙 정렬 성립완료

22와 19간 성립이 안되서 한번 더 바꿔줘

1. 최대힙 구성(0번째 인덱스가 최대값) 2. 최대값을 배열 맨 마지막에 둬 3. 인덱스 n, 2n, 2n+1간 대소관계 보고 최대힙 수행 => 이 과정을 재귀함수로

import random

def makeheap(unsorted, index, heap_size):
  print("unsorted : ", unsorted)
  largest=index
  left_index = 2 * index 
  right_index = 2 * index +1

  if left_index < heap_size and unsorted[left_index]>unsorted[largest]: 
    largest = left_index
  elif right_index < heap_size and unsorted[right_index]>unsorted[largest]:
    largest = right_index

  if largest != index:
    unsorted[largest], unsorted[index]=unsorted[index], unsorted[largest]
    makeheap(unsorted, largest, heap_size)

def heap_sort(unsorted):
  print("before max heap : ", unsorted)
  n=len(unsorted)
  for i in range(n//2-1, -1, -1):
    makeheap(unsorted, i, n)

  print("*" * 100)
  print("after max heap ", unsorted)
  print("*" * 100)

  for i in range(n-1, 0, -1):
    unsorted[0], unsorted[i]=unsorted[i], unsorted[0]
    makeheap(unsorted, 0, i)
  return unsorted

 

 

이제 3주차 백준 풀러 가볼까나,,