<자료구조>힙 (Heap)

힙 개념

우선순위 큐를 위해 만들어진 자료구조이다.

우선순위 큐(Priority Queue)?

• 우선순위의 개념을 큐에 도입한 자료구조
• 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다

• 완전 이진 트리의 일종이다.
• 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조로 반정렬 상태이다.
• 힙 트리는 중복된 값을 허용한다. (이진 탐색 트리는 중복값 허용X)

특성

• 배열의 형태로 데이터를 관리한다.
• 노드를 삽입하면 배열(트리)의 가장 마지막에 삽입.
• Top에 위치한 최대값/최솟값을 O(1)의 복잡도로 리턴.
• 오직 Parent, Child의 비교 규칙만 준수한다.

배열로 저장된 데이터

배열의 인덱스가 트리의 각 노드위치를 나타낸다.

• 인덱스 0 은 연산하기 편하게 더미값으로 둔다.
  노드는 인덱스 1 부터 시작.(출력 시에도 인덱스 1 부터)
• 현재 노드 인덱스: i
• 부모 노드 인덱스: i / 2
• 왼쪽 자식 노드 인덱스: (i * 2)
• 오른쪽 자식 노드 인덱스: (i * 2) + 1
  (형제노드의 순서는 상관 없고 데이터가 추가삽입될 땐 최하단왼쪽부터 채워진 후 정렬된다.)

힙 활용 예시

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

Heap 의 전체 시간복잡도 : O(N log N)
탐색 시간 복잡도 : O(1)
삽입/삭제 시간 복잡도 : O(log N)

최소 힙 Min_Heap

최상위 루트노드가 최소값이다.

최소 힙의 값 추가/삽입

최하단 왼쪽에 추가하여 재정렬된다.

최소 힙의 값 삭제

최소값(최상단 루트노드)를 반환하고 재정렬된다.

최대 힙 Max_Heap

최상위 루트노드가 최대값이다.

최대 힙의 값 추가/삽입

최하단 왼쪽에 추가하여 재정렬된다.

최대 힙의 값 삭제

최대값(최상단 루트노드)를 반환하고 재정렬된다.