4. heap, priority queue, union find

Heap

 

자료구조의 일종으로 Tree의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree 이다. 배열에 트리의 값들을 넣어줄 때, 1번 index 부터 루트노드가 시작된다. 힙에는 Max heap과 Min heap 두 종류가 있다.

 

Max Heap 이란, 각 노드의 값이 해당 children의 값보다 크거나 같은 complete binary tree를 말한다.

 

Max Heap 에서 최대값을 찾는데 필요한 시간복잡도는 O(1)이다. 하지만 heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 여기서 heap은 맨 마지막 노드를 루트 노드로 대체한 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우엔 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.

 

코드

 

힙(heap)의 삽입

 

void push(int x) {
	heap[++count] = x;
    
    int child = count;
    int parent = child/2;
    
    while(child > 1 && heap[child] > heap[parent]) {
    	swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
}

힙(heap)의 삭제

 

int pop() {
	int ret = heap[1];
    
    swap(&heap[1], &heap[count]);
    count--;
    
    int parent = 1;
    int child = parent*2;
    
    if(child + 1 <= count)
    	child = (heap[child] > heap[child+1]) ? child : child+1;
        
    while(child <= count && heap[child] > heap[parent]) {
    	swap(&heap[child], &heap[parent]);
        parent = child;
        child = parent * 2;
        
        if(child + 1 <= count)
        	child = (heap[child] > heap[child+1]) ? child : child + 1;
            
        }
        
        return ret;
  }

 

Union Find

 

Disjoint set을 표현할 때 사용하는 독특한 형태의 자료구조로, 공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 트리형 자료구조

 

1. Union (합치기) : 두 원소 a, b가 주어질 때, 이들이 속한 두 집합을 하나로 합친다.

2. Find (찾기) : 어떤 원소 a가 주어질 때, 이 원소가 속한 집합을 반환한다.

 

int find(int u) {
	if(u == parent[u]) return u;
    
    int p = find(parent[u]);
    parent[u] = p;
    return p;
}

void merge(int a, int b) {
	a = find(a);
    b = find(b);
    
    if(a != b)
    	parent[b] = a;
}