[자료구조] 힙(Heap)

출처 : gmlwjd9405.github.io/2018/05/10/data-structure-heap.html를 참고하여 작성하였습니다.

 

" 우선순위 큐를 위해 만들어진 자료구조 "

 

(우선순위 큐가 뭔데요? 우선순위의 개념을 큐에 도입한 자료구조로서, 우선순위가 높은 데이터가 큐에서 먼저 나가게 된다.)

1. 힙이란?

• 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
• 여러개의 값중 최댓값이나 최솟값을 빠르게 찾아내도록 고안됨
• 부모노드의 키값이 자식노드의 키값보다 항상 크거나(혹은 작은) 이진트리이다.
• 힙 트리에서는 중복된 값을 허용한다.

2. 힙의 종류

• 최대힙 (Max Heap)
  • key(부모) >= key(자식)
  • 숫자로 생각하면 큐에서 나가는 순서가 내림차순이 되는것이다.
• 최소힙 (Min Heap)
  • key(부모) <= key(자식)
  • 숫자로 생각하면 큐에서 나가는 순서가 오름차순이 되는것이다.

출처 : https://ahribori.com/article/5952f94f22eced098cbd8e3c

• 노드간 키값의 대소관계는 부모/자식간에만 성립하고, 형제노드 사이에는 대소관계가 정해지지 않는다!

3. 힙의 구현

• 배열에 힙을 저장한다. (노드번호는 1부터 시작하므로 쉬운구현을 위해 0번째 인덱스는 사용하지 않는다.)
• 특정위치의 노드번호는 변하지 않는다.

4. 힙의 삽입, 삭제

• 삽입
  • 힙에 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
  • 새로운 노드를 부모노드와 교환해서 힙의 성질을 만족시킨다.
  • 자바코드

void insert_max_heap(int x) {

maxHeap[++heapSize] = x; // 힙크기 하나 증가후 새로운노드 삽입

for (int i=heapSize; i>1; i/=2) { // 자식노드가 왼쪽이든 오른쪽이든 부모노드는 자식노드를 2로나눈것의 몫이므로 
	
    if (maxHeap[i/2] < maxHeap[i]){
    	swap(i/2, i);
   	} else {
    	break;
    }
   }
  }
   	

• 삭제
  • 최대힙에서 최댓값은 루트노드이므로 루트노드가 삭제된다.
  • 삭제된 루트노드의 빈자리에는 최대힙의 마지막 노드를 가져온다.
  • 힙을 재구성한다.

힙 관련 백준 알고리즘문제 :

www.acmicpc.net/problem/1927

1927번: 최소 힙

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

[자료구조] 힙(heap)이란 - Heee's Development Blog