[자료구조] 힙(Heap)

힙(Heap)

• 완전 이진트리 기반의 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 우선순위 큐를 위해 만들어진 자료구조
• 반정렬상태(느슨한 정렬상태) 유지
  • 큰 값이 상위에 있고 작은 값이 하위에 있는 정도
• 중복된 값 허용

힙의 종류

• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진트리
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 이진트리

힙의 활용

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서의 작업 스케쥴링
• 수치 해석적인 계산

힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열
• 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음
  • (ex 루트 노드(1)의 오른쪽 노드 번호는 항상 3)
• 부모 노드와 자식 노드의 관계
  • 왼쪽 자식 index = (부모 index) * 2
  • 오른쪽 자식 index = (부모 index) * 2 + 1
  • 부모 index = (자식 index) / 2

힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킴

(이미지 출처 : https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap)

 

힙의 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제
   
   • 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옴
3. 힙을 재구성

(이미지 출처 : https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99Heap)

 

힙 정렬(heap sort) 알고리즘

• 가장 큰 값이 루트에 위치하는 특징을 이용하여 정렬하는 알고리즘
• 가장 큰 값인 루트를 꺼내는 작업 반복하고 그 값을 늘어놓으면 배열 정렬 완료
• 시간복잡도는 O(NlogN)
• 동작 과정
  1. 1. root를 꺼냄
     2. 마지막 요소를 root로 이동
     3. 자기보다 큰 값을 가지는 자식 요소와 자리를 교환하며 내려가는 작업을 반복
        • 이때 자식의 값이 자기보다 작거나 리프(leaf)에 다다르면 종료

(이미지 출처: https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99%EC%A0%95%EB%A0%ACHeap-Sort)