힙 정렬

힙을 이해하기 위해서는 이진 트리를 이해할 필요가 있다. 이진 트리란 모든 노드의 자식의 노드가 2개 이하인 구조를 말한다. 좀 더 나아가 완전 이진 트리는 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진 트리입니다. 항상 왼쪽 자식 노드부터 데이터가 들어갑니다.

최대 힙 트리 / 최소 힙 트리를 구성해 정렬.

• 정렬해야 할 n개의 요소들로 완전 이진 트리 형태로 만든다.
• 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장.
• 삭제되는 요소들은 값이 감소되는 순서로 정렬

힙 정렬의 특징은 시간 복잡도가 좋은 편(O(nlogn)이고, 가장 유용한 경우는 전체 자료를 정렬하는 것보다 가장 큰 값들 몇 개만 필요할 때이다.

알고리즘

• 구현이 간단하지만 비효율적인 방법
  삽입 / 선택 / 버블 정렬
• 복잡하지만 효율적인 방법
  퀵 / 힙 / 합병 / 기수 정렬
  

흔히 사람들은 기회를 기다리고 있지만 기회는 기다리는 사람에게 잡히지 않는 법이다. 우리는 기회를 기다리는 사람이 되기 전에 기회를 얻을 수 있는 실력을 갖춰야 한다. 일에 더 열중하는 사람이 되어야한다. -안창호