이 포스팅의 알고리즘 강의는 이곳에서 보실 수 있습니다.

Heap과 Heapsort

• 최악의 경우 시간복잡도 O(nlog2n)
• mergesort와의 차이점은 추가 배열이 필요하지 않다는 것.
• 이진 힙(binary heap) 자료구조를 사용.

Heap의 정의

• Heap은 complete binary Tree여야 한다.

Tree는 계층적 관계를 말한다.

• 부모가 존재하지않는 가장 위에 위치한 노드는 root노드라고 말한다.
• 자식이 없는 노드들을 leaf노드라고 한다.
• 이진 트리는 부모노드가 자식노드를 최대 2개 가지는 것을 말한다.
• level은 루트(level1)로 부터 얼마나 아래로 내려와 있는지를 말한다.
• Full vs Complete
  • Full은 마지막 노드들이 가득 차 있는 형태 -> Full은 그 자체로 Complete이다.
  • Complete는 마지막 레벨에 가장 오른쪽부터 연속된 몇 개의 노드가 비어있는 것.

Heap의 표현

• 힙은 일차원 배열로 표현가능 : A[1 .. n] (n은 노드갯수)

MAX-HEAPIFY

Recursion 사용

Recursion 미사용

힙 정렬을 만드는 방법

힙의 응용: 우선순위 큐

• 자료구조에서 배운 큐는 FIFO 큐이다. (first in first out)
• 우선순위 큐란 데이터를 insert할 수 있는 주머니인데 여기서 안에 들어있는 데이터가 우선순위라는 것을 가지고 있어서 우선순위가 가장 높은 순으로 꺼내는 것을 말한다.
• Insert 알고리즘은 힙 트리의 마지막에 문제 노드를 넣고 값을 부모와 비교해서 올리거나 그대로 둔다.
• Extract_max() 알고리즘은 최대값을 찾는 것인데 Max heap은 최대값은 항상 root에 존재한다. 최대값을 추출하고 heap의 개수를 한개 줄여야 하는데 이때 루트의 값을 추출하고 제일 마지막에 있는 노드의 값을 루트의 값에 넣는다.(마지막 노드는 삭제). 이러면 루트만이 힙 프로퍼티를 만족하지 않고 자식들은 힙을 만족한다. 이 상황에서 max_heapify를 적용하여 다시 힙으로 만들어준다.

Comparison sort vs Non-Comparison sort

• Comparison은 일반적으로 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘. (데이터들의 크기관계만 정의되어있으면 어떤 데이터든 적용가능)
• Non-Comparison은 정렬할 데이터에 대한 사전지식을 이용해서 정렬하는 알고리즘. (적용에 제한이 있다.)

정렬문제의 하한

• 하한(Lower bound)
  • 입력된 데이터를 한번씩 다 보기위해서 최소 O(n)의 시간복잡도가 필요.
  • 합병정렬과 힙정렬 알고리즘들의 시간복잡도는 O(nlog2n)
  • 어떤 comparison sort 알고리즘도 O(nlog2n)보다 나을수 없다.