힙?
힙은 완전 이진트리에서 키 값이 가장 큰 노드나 작은 노드를 쉽게 찾기 위해 고안된 자료구조이다. 키 값이 가장 큰 노드를 찾을 때는 최대힙, 키 값이 가장 작은 노드를 찾을 때는 최소힙으로 구현한다.
최소 힙
완전 이진 트리로 구현한다. 서브트리의 부모 노드는 자식노드보다 무조건 작거나 같고, 자식노드들은 왼쪽부터 차례로 채운다. 같은 레벨의 자식노드들 끼리의 크기는 중요하지 않다.
자식노드는 무조건 부모보다 크거나 같고, 왼쪽부터 채우기!!!
*완전 이진 트리(complete binary tree)란 자식을 왼쪽부터 차례로 채우는 이진트리이다.
힙의 구현(배열) ADT
- 공백 힙 생성 -> createHeap()
- 힙이 공백인지 검사 -> isEmpty()
- 삽입연산 -> insertHeap()
- 삭제 후 반환 연산 -> deleteHeap()
**힙에서 인덱스 관계
현재 노드 index == i
부모 노드 index == i/2
왼쪽자식 노드 index == i x 2
오른쪽자식 노드 index == i x 2 + 1
삽입연산
이진트리의 형태를 만족하기 위하여 현재 노드 다음 자리에 자리를 만들고, 부모와 비교하면서 최소힙의 조건을 만족하는 자리를 찾아 나간다.
삭제연산
루트 노드를 삭제하여 반환한 후, 현재 가장 마지막에 있는 노드를 루트로 이동시킨 후, 자식과 비교하며 최소힙을 만족하는 자리를 찾아 나간다.
구현 코드
- 클래스 구조
const int MAX = 100001;
class Heap {
protected:
int heap[MAX]; //힙 배열
int heap_size; //힙에 들어있는 데이터
public:
Heap() { //생성자
for (int i = 0; i < MAX; i++) {
heap[i] = 0;
}
heap_size = 0;
}
bool is_empty();
void pushHeap(int val);
int popHeap();
void swap(int& a, int& b);
};- 힙이 비었는지 확인
bool Heap::is_empty() { //힙이 비어있으면 true 리턴
if (heap_size == 0) {
return true;
}
return false;
}- 힙에 데이터 Push
void Heap::pushHeap(int val) {
int curr_idx = ++heap_size; //0자리는 비워둠. 인덱스 1부터 값 삽입
int parent_idx = curr_idx / 2; //현재 순회중인 노드의 부모 인덱스
if (!is_empty()) { //비어있지 않을 때
while (parent_idx > 0 && val < heap[parent_idx]) { //자식이 부모보다 작으면
heap[curr_idx] = heap[parent_idx]; //부모를 현재 순회중인 인덱스 위치에 넣고
curr_idx = parent_idx; //부모로 이동
parent_idx /= 2;
}
}
heap[curr_idx] = val; //맞는 위치에 삽입
}- 힙에서 데이터 Pop
int Heap::popHeap() {
int return_val = 0;
if (!is_empty()) { //비어있지 않을 때
int parent_idx = 1;
int child_idx = parent_idx * 2;
return_val = heap[1]; //힙에서 루트에 있는 값이 최솟값이므로 반환값.
heap[1] = heap[heap_size--]; //힙에서 마지막에 있는 값을 루트로 옮김.
while (child_idx <= heap_size) {
if (child_idx + 1 <= heap_size && heap[child_idx + 1] < heap[child_idx]) { //오른쪽자식이 된쪽자식보다 작으면 오른쪽자식으로 이동해서 본인과 비교
child_idx++;
}
if (heap[parent_idx] < heap[child_idx]) break; //본인 자리 찾았으면 탈출
swap(heap[parent_idx], heap[child_idx]);
parent_idx /= 2; //자식으로 이동
child_idx = parent_idx * 2;
}
}
return return_val;
}전체 코드(백준 1927번 최소 힙)
#include <iostream>
using namespace std;
const int MAX = 100001; //처음에 BST랑 완전이진트리 헷갈렸음. 완전이진트리는 그냥 왼쪽에서부터 자식을 채우는 것!! 다른 규칙 없음
class Heap {
protected:
int heap[MAX]; //힙 배열
int heap_size; //힙에 들어있는 데이터
public:
Heap() { //생성자
for (int i = 0; i < MAX; i++) {
heap[i] = 0;
}
heap_size = 0;
}
bool is_empty();
void pushHeap(int val);
int popHeap();
void swap(int& a, int& b);
};
int main(void) {
int t_case = 0, input = 0;
Heap heap;
cin >> t_case;
for (int i = 0; i < t_case; i++) { //연산 수만큼 반복
cin >> input;
if (input == 0) {
cout << heap.popHeap() << "\n";
}
else if (input > 0) {
heap.pushHeap(input);
}
}
return 0;
}
bool Heap::is_empty() { //힙이 비어있으면 true 리턴
if (heap_size == 0) {
return true;
}
return false;
}
void Heap::pushHeap(int val) {
int curr_idx = ++heap_size; //0자리는 비워둠. 인덱스 1부터 값 삽입
int parent_idx = curr_idx / 2; //현재 순회중인 노드의 부모 인덱스
if (!is_empty()) { //비어있지 않을 때
while (parent_idx > 0 && val < heap[parent_idx]) { //자식이 부모보다 작으면
heap[curr_idx] = heap[parent_idx]; //부모를 현재 순회중인 인덱스 위치에 넣고
curr_idx = parent_idx; //부모로 이동
parent_idx /= 2;
}
}
heap[curr_idx] = val; //맞는 위치에 삽입
}
int Heap::popHeap() {
int return_val = 0;
if (!is_empty()) { //비어있지 않을 때
int parent_idx = 1;
int child_idx = parent_idx * 2;
return_val = heap[1]; //힙에서 루트에 있는 값이 최솟값이므로 반환값.
heap[1] = heap[heap_size--]; //힙에서 마지막에 있는 값을 루트로 옮김.
while (child_idx <= heap_size) {
if (child_idx + 1 <= heap_size && heap[child_idx + 1] < heap[child_idx]) { //오른쪽자식이 된쪽자식보다 작으면 오른쪽자식으로 이동해서 본인과 비교
child_idx++;
}
if (heap[parent_idx] < heap[child_idx]) break; //본인 자리 찾았으면 탈출
swap(heap[parent_idx], heap[child_idx]);
parent_idx /= 2; //자식으로 이동
child_idx = parent_idx * 2;
}
}
return return_val;
}
void Heap::swap(int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}문제점
위 코드를 Visual Studio에서 돌려보면 잘 되는데, 백준에 제출하면 시간 초과가 계속 난다. cin의 속도 문제인줄 알고 scanf로 바꾸어 해보았는데, 되지 않았다. C++ STL priority_queue를 이용해야 하는 것 같다.
Record What I Learned