[자료구조] Heap이란?

Heap이란?

 

우선순위 큐를 만들기 위하여 만들어진 자료구조

 

 

 

우선순위 큐

 

말 그대로 "큐" + "우선 순위"이다.

 

*큐 : 선입선출 방식의 자료구조로 먼저 들어간 자료가 먼저 나오는 방식이다.

*우선선위 큐 : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

(생활 예시)

응급실을 생각해보자. 내가 먼저 왔지만 위급한 정도에 따라서 나중에 온 환자가 먼저 진료를 받을 수도 있다.

 

(소프트웨어 예시)

안드로이드는 메모리가 부족할 경우 시스템에 의해서 프로세스가 종료될 수 있는데 우선순위에 따라서 종료되는 프로세스가 결정된다.

즉, 먼저 실행된 프로세스가 먼저 종료되는 것이 아니라 우선순위에 따라서 결정되는 것이다.

*실제로 이게 힙으로 구현되어 있는지는 모르겠지만... 힙을 활용해서도 구현할 수 있다.

 

 

 

힙(Heap)의 특징

 

앞서 말한 것처럼 힙은 우선순위 큐를 구현하기 위한 방법 중 하나로 다음과 같은 특징을 가진다.

 

• 완전 이진 트리 : 왼쪽부터 차례대로 삽입하는 트리
• 반정렬 상태 : 느슷한 정렬 상태로, 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다. 
• 중복된 값을 허용

 

 

 

종류

 

 

최대 힙

- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 

 

최소 힙 

- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

 

 

구현

- 기본적으로 배열을 사용한다.

 

- 인덱스간의 일정한 규칙성을 부여하면 배열을 트리 구조처럼 활용할 수 있다.

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

 

(최소 힙)

 

1. 삽입

 

1) 힙의 마지막 값으로 삽입한다.

2) 부모의 값과 비교하며 더 작을 경우 부모와 자리를 바꾼다.

    *변경된 이후에도 그 노드의 부모 노드와 비교

 

 

2. 제거

 

1) 루트 노드(최상단의 노드)를 pop한 뒤 제거

2) 새로운 루트 노드로 힙의 마지막 값이 올라온다.

3) (변경된 루트 노드 > 자식 노드)이면 루트 노드와 자식 노드 위치 변경

    *변경된 이후에도 그 노드의 자식 노드와 비교

 

 

(구체적인 코드는 아래 블로그를 참고)

 kim6394.tistory.com/222

 

 

 

참고 사이트

gmlwjd9405.github.io/2018/05/10/data-structure-heap.html