[자료구조] Heap

Heap(힙)이란

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조

최댓값이나 최솟값을 빠르게 찾아낸다.

 

* 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조

 

힙(heap)의 종류

1. 최대 힙

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

2. 최소 힙

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

힙(Heap)의 삽입

1. 새로운 요소가 들어오면 마지막 노드에 삽입.

2. 새로운 노드를 부모 노드와 비교하며 교환한다.

 

힙(Heap)의 삭제

1. 최대 힙의 경우 삭제되는 노드는 루트 노드이다.

* 최대 힙은 최댓값, 최소 힙은 최솟값을 삭제한다.

2. 삭제된 루트노드 자리에 마지막 노드를 가져온다.

3. 힙을 재구성한다.

 

 

코드에 적용하기 [c++]

STL priority_queue를 사용한다.

#include <queue>

 

priority_queue<int, vector<int>, less<int>> q; // Max Heap

priority_queue<int, vector<int>, greater<int>> q; //Min Heap

 

• q.push(value); - 큐에 값을 넣습니다. 
• q.top(); - min heap은 큐에서 가장 작은 값, max heap은 큐에서 가장 큰 값을 리턴합니다.
• q.size(); - 큐에 몇개가 들어있는지 리턴합니다.
• q.empty(); - 큐에 1개라도 들어있으면 true, 아무것도 없으면 false를 리턴합니다.
• q.pop(); - min heap은 큐에서 가장작은 값, max heap은 큐에서 가장 큰 값을 큐에서 제거합니다.
  
  

 

[STL priority_queue 사용법] dyngina.tistory.com/24