11.ch6.pdf

• merge sort → faster but lots of memory
• insertion sort → sort in place, constant memory
  • sort in place; 원소들의 개수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘.
  • 추가적인 메모리가 더 필요하지 않음.

⇒ Heap sort

• 장점들만 모아놓음. (time, memory)

Heaps

1. nearly completely binary tree

• completely binary tree (혹은 full b.t)
• nearly complete binary tree (혹은 complete b.t)
  • 예시에서, heap은 보통 배열로 구현된다.
  • A = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
  • 알차게 차있다면 포인터가 아니라 배열을 사용할 수 있음.
  • index만 가지고 operation이 가능하다.

Nearly Complete binary tree

• root node = A[1]
• Node i = A[i]
• parent of node i = A[i/2]
• left child of node i = A[2i]
• right child of node i = A[2i+1}

Heap

• Max tree
  • 자식보다 키값이 작지 않음.
• min tree
  • 자식보다 키값이 크지 않음
• max-heap
  • max tree +nearly complete binary tree
• min-heap
  • min tree + nearly complete binary tree