[자료구조] heap

Heap

• 최댓값 및 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조
• '완전이진트리(completely binary tree)'를 기초로 함
• 중복된 값을 허용 ( cf. 이진 탐색 트리(binary search tree)는 중복값 허용 x )
• A가 B의 부모 노드이면 A의 key 값과 B의 key 값 사이엔 대소관계가 성립
  • 최대힙 - A key 값 > B key 값
  • 최소힙 - A key 값 < B key 값
• 위 성질로 인해 항상 반정렬 상태가 유지됨

 

---

Heap 구현

• 힙은 보통 '배열'로 구현됨

( 부모 노드 ) = ( 자식 노드 ) / 2
( 왼쪽 자식 노드 ) = ( 부모 노드 ) * 2
( 오른쪽 자식 노드 ) = (부모 노드) * 2 + 1

index	0	1	2	3	4	5	6	7
value	x	9	7	6	5	4	3	2

 

Insert :

힙에 새로운 노드를 추가, 힙의 성질이 유지되도록 재정렬

1. 새로운 노드를 힙의 가장 마지막에 추가
2. 추가된 새로운 노드를 부모 노드와 비교하여 부모 노드보다 값이 클 경우(최대힙 기준) 부모 노드와 자식 노드의 값을 swap
3. 올바른 위치에 도달할 때까지 2번 동작을 반복

#include <vector>
using namespace std;

vector<int> heap;
heap.push_back(0); // 힙의 루트 인덱스를 1로 하기 위함
int size = 0;
const int root_idx = 1;

bool my_cmp(const int a, const int b) {
	return (a < b); // 최대힙
	// return (a > b); // 최소힙
}

void my_swap(int &a, int &b) {
	int tmp = a; a = b; b = tmp;
}

void push(int x) {
	// 힙의 마지막에 새로운 노드 추가
	heap.push_back(x); size++;

	// 부모 노드와 값을 비교하며 새로운 노드를 올바른 위치로 재정렬
	int cur = size;
	while (cur > root_idx) {
		if (!my_cmp(heap[cur / 2], heap[cur])) break;
		my_swap(heap[cur / 2], heap[cur]);
		cur /= 2;
	}
}

 

Delete :

최댓값(최대힙 기준), 즉 힙의 루트를 제거

1. 루트 A와 힙의 마지막 노드 B를 swap한 후 마지막 노드가 된 A를 제거
2. B를 자식 노드와 비교하여 자식 노드보다 값이 작을 경우(최대힙 기준) swap
   1. 왼쪽 자식 노드와 오른쪽 자식 노드가 모두 있을 경우, 둘 중 더 큰 값(최대힙 기준)을 가진 노드와 비교
   2. 왼쪽 노드만 있을 경우, 왼쪽 노드의 값과 비교
3. 올바른 위치에 도달할 때까지 2번 동작을 반복

 

#include <vector>
using namespace std;

vector<int> heap;
heap.push_back(0); // 힙의 루트 인덱스를 1로 하기 위함
int size = 0;
const int root_idx = 1;

bool my_cmp(const int a, const int b) {
	return (a < b); // 최대힙
	// return (a > b); // 최소힙
}

void my_swap(int &a, int &b) {
	int tmp = a; a = b; b = tmp;
}

void pop() {
    // 마지막 노드와 루트 노드를 swap한 후, 마지막에 위치한 루트 노드를 제거
    my_swap(heap[size], heap[root_idx]);
    heap.pop_back(); size--;

    // 루트에 위치된 노드를 자식 노드와 비교하며 올바른 위치로 재정렬
    int cur = root_idx;
    while (cur < size) {
        int child_idx = cur * 2;
        if (cur * 2 + 1 <= size && my_cmp(heap[child_idx], heap[cur * 2 + 1]))
            child_idx = cur * 2 + 1;

        if (child_idx > size || !my_cmp(heap[cur], heap[child_idx])) break;
        my_swap(heap[cur], heap[child_idx]);
        cur = child_idx;
    }
}

 

Total Code :

#include <vector>
using namespace std;

bool my_cmp(const int a, const int b) {
	return (a < b); // 최대힙
	// return (a > b); // 최소힙
}

void my_swap(int &a, int &b) {
	int tmp = a; a = b; b = tmp;
}

class Heap {
    vector<int> heap;
    int size;
    const int root_idx = 1;

public:
	Heap() {
    	heap.push_back(0); // 힙의 루트 인덱스를 1로 하기 위함
    	size = 0;
    }
	void push(int x) {
        // 힙의 마지막에 새로운 노드 추가
        heap.push_back(x); size++;

        // 부모 노드와 값을 비교하며 새로운 노드를 올바른 위치로 재정렬
        int cur = size;
        while (cur > root_idx) {
            if (!my_cmp(heap[cur / 2], heap[cur])) break;
            my_swap(heap[cur / 2], heap[cur]);
            cur /= 2;
        }
    }
    void pop() {
        // 마지막 노드와 루트 노드를 swap한 후, 마지막에 위치한 루트 노드를 제거
        my_swap(heap[size], heap[root_idx]);
        heap.pop_back(); size--;

        // 루트에 위치된 노드를 자식 노드와 비교하며 올바른 위치로 재정렬
        int cur = root_idx;
        while (cur < size) {
            int child_idx = cur * 2;
            if (cur * 2 + 1 <= size && my_cmp(heap[child_idx], heap[cur * 2 + 1]))
                child_idx = cur * 2 + 1;

            if (child_idx > size || !my_cmp(heap[cur], heap[child_idx])) break;
            my_swap(heap[cur], heap[child_idx]);
            cur = child_idx;
        }
    }
    int top() { return heap[root_idx]; }
    bool empty() { return (size <= 0); }
};