힙과 힙 정렬 (Heap & Heap Sort) 요약 및 관련 자료

Reading time ~3 minutes

알고리즘을 구글링을 하다보면 자세한 설명 없이 그림 몇 개와 개념적인 내용만 나열해 놓은 정리 위주의 글들이 많다. 이런 글들은 대부분 개념을 자세히 모르고 있으면 이해하기가 힘들다. 특히 시간 복잡도를 구하는 과정에 대한 내용은 찾아보기 힘들다. 힙 정렬에 대해 이해하기 쉽게 정리된 글들이 있어서 소개하려고 한다. 해당 링크와 더불어 이해한 내용을 간단하게 요약했다. 힙 정렬에 대한 자세한 내용은 첨부된 링크를 참고하길 바란다.


힙 정렬에 대한 좋은 글들

자세하고 이해하기 쉽게 잘 정리된 글들이다. 글을 쓰신 분의 노력이 보여서 감탄했다.

  • https://zeddios.tistory.com/56
  • https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/


요약

힙 (heap)

완전이진트리 (complete binary tree)

최대 두개의 자식노드를 가지고 마지막 노드를 제외한 모든 레벨의 노드들읜 꽉 채워진 완전이진트리의 특징을 가진다.

배열로 표현이 가능하다.

  • 인덱스 0부터 시작하는 경우
    • 왼쪽 자식 노드 = 2 X 부모 노드 + 1
    • 오른쪽 자식 노드 = 2 X 부모 노드 + 2
  • 인덱스 1부터 시작하는 경우
    • 왼쪽 자식 노드 = 2 X 부모 노드
    • 오른쪽 자식 노드 = 2 X 부모 노드 + 1


Heapify

heapify란 주어진 데이터를 힙 성질을 만족하도록 만드는 것을 뜻한다. 하나의 데이터에 대해 heapify의 시간복잡도는 최악의 경우를 따져봤을 때 루트 노드에서 잎새 노드까지 값을 모두 비교하는 것으로 트리의 높이인 O(logN) 이 된다.


힙 정렬 (Heap Sort)

  1. 힙 정렬이란 주어진 데이터를 최대 힙 혹은 최소 힙 트리로 구성한다.
  2. 루트 노드와 말단 노드를 교환한다.
  3. 다운힙 수행 (순서 조건을 만족하도록 만드는 방법) : 마지막 노드를 제외한 트리에 대해 루트 노드에 들어간 새로운 값의 적절한 위치를 찾아준다.
  4. 원소의 개수 만큼 2와 3 과정을 반복한다.


힙 정렬 시간복잡도

Build Heap(주어진 데이터를 힙으로 만든다.)

  1. 모든 데이터를 차례로 힙에 삽입한다. (이 방법 보다는 더 효율적인 2번의 방법을 사용한다.)
    • 데이터 하나에 대해 시간복잡도는 O(logN)
    • 전체 데이터 N에 대해 모두 수행하므로 O(NlogN)
    • 구하는 방법 : log1 + log2 + log2 + log4 + log4 + log4 + log4 + log8 + … + logN < NlogN
  2. N/2 개의 노드에 대해 heapify를 수행한다. (자세한 내용은 위의 링크를 참고.)
    • 시간 복잡도 O(N)


힙 정렬

시간 복잡도
= Build Heap + N번의 DownHeap
= O(N) + O(N * logN)
= O(NlogN)

Java 우선순위 큐(Priority Queue) 와 Comparable, Comparator

우선순위 큐(Priority Queue)우선순위 큐는 먼저 들어간 데이터가 먼저 나오는 일반적인 큐와는 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 가장 먼저 나온다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이다. 데이터를 삽...… Continue reading