[Data Structure] #5-1 Heap

알고리즘 문제를 풀 다 보면 최소값 혹은 최대값을 뽑아내야 할 때가 있다. 물론 쓰지 않아도 답은 나오지만 Time Limited 가 걸리는 문제가 있다. 이럴 때 쓰는 것이 힙이다. 물론 그 외에도 Kruskal 알고리즘 같은 곳에도 쓰이고 다양하게 쓰인다.

#include <iostream>
#define MAX_VERTICES 100

using namespace std;

int h[MAX_VETICES];
int h_size;
void h_init()
{
h_size = 0;
}
void insert(int v)
{
int i = ++h_size;
while (i != 1 && v < h[i / 2]){
h[i] = h[i / 2];
i /= 2;
}
h[i] = v;
}
int remove()
{
int item = h[1];
int temp = h[h_size--];
int p = 1;
int c = 2;
while (c <= h_size){
if (h[c] > h[c + 1]) c++;
if (temp <= h[c]) break;
h[p] = h[c];
p = c;
c *= 2;
}
h[p] = temp;
return item;
}
int main()
{
h_init();
insert(8);
insert(9);
insert(1);
insert(2);
insert(0);
insert(4);
int n = h_size;
for (int i = 1; i <= n; i++){
printf("%d\n", remove());
}
return 0;
}