최소, 최대 힙 (min & max heap)

출처:https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

자료구조 ‘힙(heap)’이란?

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다.
큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
key(부모 노드) >= key(자식 노드)

최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
key(부모 노드) <= key(자식 노드)

 

힙의 삽입과 삭제

최소힙을 기준으로 했다. 먼저 트리를 배열로 지정하게 될 경우

왼쪽 자식노드의 인덱스 = 부모노드의 인덱스*2

오른쪽 자식노드의 인덱스 = 부모노드의 인덱스*2 +1

부모노드의 인덱스 = 자식노드의 인덱스/2

인 관계를 유지하고 있으며 이를 일관성있게 유지시키기 위해서는 루트 노드의 인덱스를 1부터 지정해주면 좋다.

 

힙의 삽입:

반복문 조건 while (idx/2>0) // 부모노드 인덱스 즉 1 까지의 범위 안에서

삽입은 먼저 넣고자하는 key값을 제일 마지막 단말노드에 넣고 부모노드와 값을 비교해 가면서 부모노드보다 작을경우 값을 계속해서 스왑해 나가며 올리고 key값이 부모노드 값보다 계속해서 작다고 가정하면 루트노드까지 반복한다.

 

힙의 삭제:

먼저 루트노드에 있는 값을 삭제하고 제일 마지막에 있는 단말노드를 루트노드로 올린다. 그리고 최소힙을 적용하여 다시 힙구조를 정렬시키는 과정이다.

힙의 삭제는 3가지 경우로 나눌 수 있다. 트리의 자식이 2개인 경우, 1개인 경우, 없을 경우

 

트리의 자식이 2개인 경우: 자식의 왼쪽값<= 자식의 오른쪽 값 이면 왼쪽 자식을 선택하고 부모노드>선택된 자식 이면 위치를 swap해준다. 이과정을 반복하되, 종료조건으로 idx*2+1 <=Size안에 들어있어야 하고 만약 중간에 부모노드값이 자식노드보다 작거나 같으면 반복을 중지하고 종료한다.

 

트리의 자식이 1개인 경우 - 왼쪽 자식밖에 없다. 따라서 왼쪽 자식과 비교후 swap을 할지 말지 정하고 종료 시키면 된다.

 

자식이 없는 경우: 바로 반복문을 종료 시킨다.

 

최대힙도 최소힙과 마찬가지로 같은 구조이며 다만 부등호만 최소힙과 반대로 해준다고 생각하면 된다.

 

 

관련문제:https://www.acmicpc.net/problem/1927

1927번: 최소 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

#1927 최소힙 소스코드