DS Certi (Pro) Heap (기본 문제) - jjin-choi/study_note GitHub Wiki

§ Day 04 (Max Heap)

□ Heap

  • Max heap (최대 힙)

    • 완전 이진 트리 : 이진 트리의 원소가 왼쪽부터 채워짐. 더 채울 수 없는 경우 새로운 레벨의 왼쪽부터 채움

    • 부모 노드의 값 >= 자식 노드의 값

    • 배열의 1번부터 채우자 !

  • 포인터

    • 그 동안 int 형 포인터 / 구조체 포인터를 사용해 왔는데, (ex. int* A, _node* next)
    • 그 변수가 저장되어 있는 메모리가 항상 있고 그 메모리 위치를 가리키는 게 포인터이기 때문에
    • 함수 포인터도 사용 가능 ! 해당 함수의 위치가 기록되어 있음.
    • 선언을 할 때에는 return type 과 argv type 을 맞추어 선언해주면 된다.
bool (*comp) (int, int);  // 함수 포인터 선언
bool maxComp (int a, int b) { return a > b; }
bool minComp (int a, int b) { return a < b; }

comp = maxComp;
comp(1, 2)

□ [P] 힙 정렬

#include <stdio.h>

const int MAX = (int)(5e5 + 3);

int heap[MAX];
int N, in, hn;

void swap(int& a, int& b) { int temp = a; a = b; b = temp; }
bool comp(int a, int b) { return (a > b); }

void push_heap(int num) {
	heap[++hn] = num;
	// c : 자식 노드 
	for (int c = hn; c > 1; c /= 2) {
		// comp (앞, 뒤) : 앞이 우선순위가 높으면 바꿔 주겠다. 
		if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
		else break;
	}
}

int pop_heap() {
	int ret = heap[1];

	swap(heap[1], heap[hn--]);
	for (int c = 2; c <= hn; c *= 2) {
		// 일단 오른쪽이 있으면 (c < hn) 왼쪽과 오른쪽 비교 
		if (c < hn && heap[c + 1] > heap[c]) c++;
		
		// 부모와 우선 순위 높은 자식 비교 
		if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
		else break;
	}
	return ret;
}

void print_heap() {
	for (int n = 1; n <= N; n++)
		printf("%d ", heap[n]);
	printf("\n");
}

int main()
{	
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	for (int n = 0; n < N; n++) {
		scanf("%d ", &in);
		push_heap(in);
	}

	print_heap();
	for (int n = 1; n <= N; n++) pop_heap();
	print_heap();

	return 0;
}

□ [Q] 모든 수의 합

#include <stdio.h>

typedef unsigned long long ull;
const int MAX = (5000 + 3);
int N, in;
ull ans;

bool max(int x, int y) { return x > y; }
bool min(int x, int y) { return x < y; }
void swap(int& x, int &y) { int temp = x; x = y; y = temp; }

struct priority_queue {
	int hn;
	int heap[MAX];
	bool (*comp)(int, int);

	void init(int type) { hn = 0; comp = type ? max : min; }

	void push(int num) {
		heap[++hn] = num;

		for (int c = hn; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	int pop() {
		int ret = heap[1];
		heap[1] = heap[hn--];

		for (int c = 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
		return ret;
	}
	
	int top() { return heap[1]; }
	int size() { return hn; }
} maxpq, minpq;

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d", &N);

	minpq.init(0);

	for (int n = 0; n < N; n++) {
		scanf("%d ", &in);
		minpq.push(in);
	}

	for (int n = 0; n < N && minpq.hn > 1; n++) {
		ull sum = minpq.pop() + minpq.pop();

		ans += sum;
		minpq.push(sum);
	}

	printf("%d\n", ans);
	return 0;
}

□ [R] 못생긴 수

#include <stdio.h>

typedef unsigned long long ull;
const int MAX = 1500;
ull ugly[MAX];
int ucnt = 1, in;

void swap(ull &x, ull &y) { int temp = x; x = y; y = temp; }
bool max(ull x, ull y) { return x > y; }
bool min(ull x, ull y) { return x < y; }

struct priority_queue {
	int hn; 
	ull heap[MAX + 3];
	bool(*comp) (ull, ull);
	
	void init(int type) { hn = 0; comp = type ? max : min; }
	void push(ull num) { 
		heap[++hn] = num;
		for (int c = hn; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	ull pop() {
		if (hn <= 0) return 0;
		ull ret = heap[1];

		heap[1] = heap[hn--];
		for (int c = 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
		return ret;
	}
} minpq, maxpq;

void make_ugly_number() {
	
	int weight[3] = { 2, 3, 5 };

	minpq.push(ucnt);
	while (ucnt <= MAX) {
		ull top = minpq.pop();
		if (ugly[ucnt - 1] == top) continue;
		ugly[ucnt++] = top;

		for (int i = 0; i < 3; i++)
			minpq.push(top * weight[i]);
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	minpq.init(0);
	make_ugly_number();

	while (scanf("%d", &in) && in)
		printf("%llu\n", ugly[in]);
	
	return 0;
}

□ [S] 중간값

#include <stdio.h>

const int MAX = (2e5 + 5);
int N, M, in;

void swap(int &x, int&y) { int temp = x; x = y; y = temp; }
bool max(int x, int y) { return x > y; }
bool min(int x, int y) { return x < y; }

struct priority_queue {
	int hn;
	int heap[MAX];
	bool(*comp)(int, int);

	void init(int type) { hn = 0; comp = type ? max : min; }

	void push(int num) {
		heap[++hn] = num;

		for (int c = hn; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	int pop() {
		int ret = heap[1];
		heap[1] = heap[hn--];

		for (int c = 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
		return ret;
	}

	int size() { return hn; }
} minpq, maxpq;

int main()
{
	minpq.init(0);
	maxpq.init(1);

	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	printf("%d\n", M);

	for (int n = 0; n < N / 2; n++) {
		
		for (int i = 0; i < 2; i++) {
			scanf("%d ", &in);

			if (in < M) maxpq.push(in);
			else		minpq.push(in);
		}

		if (minpq.size() > maxpq.size()) {
			maxpq.push(M);
			M = minpq.pop();
		}
		else if (minpq.size() < maxpq.size()) {
			minpq.push(M);
			M = maxpq.pop();
		}
		printf("%d\n", M);
	}

	return 0;
}

□ [T] 질의 - 점갱신 전체 질의

  • 중간 원소 update

    • lazy update (erase / update)
      . pop 할 때 유효하지 않은 것을 버리는 방식
      . // erase //
      . 중간 원소 erase 될 때, 별도의 배열로 유효한 값인지 표시
      . top 뽑아낼 때 유효한 값인지 판별 후 유효하지 않으면 pop 하고 유효한 값 나올 때까지 반복
      . // update //
      . 중간 원소 update 될 때, update 된 정보를 heap 에 push.
      . 중복해서 들어가기 때문에 실제 정보가 저장되는 별도의 배열이 있어,
      . top 뽑아낼 때 실제 정보와 같은지 판별하여 그렇지 않다면 pop 하고 유효한 값 나올 때까지 반복

    • real time update (erase / update)
      . 이번 heap 에는 id 만 들어가고 중복되는 값이 없음.
      . 각 원소들의 heap index 를 기록하는 별도의 배열 (pos[]) 필요.
      . swap 시 heap 과 pos 둘다 swap 되어야 함.
      . 특정 id가 들어왔을 때, pos[id]를 접근하여 heap의 index를 바로 구할 수 있다.
      . // erase //
      . 중간 원소 erase 될 때, 마지막 원소를 해당 위치(pos[id])로 (지울 원소 위치) 갖고 와서 up(), down() 으로 본인 자리를 찾아감.
      . 즉, 기존 pop 와 동일한데 pop 에서 heap[1] = heap[hn--] 에서 1 이 아니라 해당 위치로..
      . // update //
      . 중간 원소 update 될 때, 해당 위치 (pos[id]) 값을 update 해주고 up(), down()으로 본인 자리를 찾아간다.

struct _priority_queue { 
   int hn;
   int heap[MAX];
   int pos[MAX]; // id 범위만큼 필요 ( 이 문제 id 는 배열의 index ) 
//  lazy  update 


#include <stdio.h>

const int MAX = (int)(1e5 + 3);
int N, Q, S[MAX];

// lazy 업데이트 할 때에는 id 가 중복되기 때문에 구조체가 필요  
struct _sequence {
	int idx;
	int val;
} seq[MAX];

template <typename _TYPE>
void swap(_TYPE &x, _TYPE &y) { _TYPE temp = x;  x = y; y = temp; }

bool max (_sequence x, _sequence y) { 
	if (x.val == y.val) return x.idx > y.idx;
	return x.val > y.val;
}

bool min(_sequence x, _sequence y) {
	if (x.val == y.val) return x.idx < y.idx;
	return x.val < y.val;
}

struct _priority_queue {
	int hn;
	_sequence heap[MAX + MAX]; // query 수도 추가해주어야 함.. ! 

	bool (*comp)(_sequence, _sequence);
	void init(int type) { hn = 0;  comp = type ? max : min; }

	void push(_sequence seq) {
		heap[++hn] = seq;

		for (int c = hn; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	void pop() {
		heap[1] = heap[hn--];

		for (int c = 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(heap[c], heap[c / 2]);
			else break;
		}
	}

	_sequence top() { 
		_sequence ret;

		while (1) {
			ret = heap[1];
			if (S[ret.idx] != ret.val) pop();
			else break;
		}
		return ret; 
	}
} minpq, maxpq;


int main()
{
	minpq.init(0);
	maxpq.init(1);

	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &Q);

	for (int n = 1; n <= N; n++) {
		scanf("%d", S + n);
		minpq.push({ n, S[n] });
		maxpq.push({ n, S[n] });
	}

	int cmd, idx, val;

	for (int q = 0; q < Q; q++) {
		scanf("%d ", &cmd);

		if (cmd == 1) {
			scanf("%d %d", &idx, &val);
			S[idx] = val;
			minpq.push({ idx, val });
			maxpq.push({ idx, val });
		}

		if (cmd == 2) {
			_sequence min = minpq.top();
			printf("%d\n", min.idx);
		}

		if (cmd == 3) {
			_sequence max = maxpq.top();
			printf("%d\n", max.idx);
		}
	}

	return 0;
}
  • real time 일 때 함수 추가할 내용
    • up() : 현재 위치부터 /=2 하면서 조건에 맞으면 swap
    • down() : 현재 위치가 parent 가 되기 때문에 parent * 2 부터 *=2 하면서 조건에 맞으면 swap
    • erase() : (pop 형태와 비슷) pos[val] 로 hidx 가져와서 hidx 와 hn-- 에 대해 swap 후 up / down
    • update() : (push 형태와 비슷) pos[val] 로 hidx 가져와서 up / down
    • swap() : heap 과 pos 둘 다 값 변경해주도록
struct _priority_queue {
	int hn;
	int heap[MAX]; // val 저장. 실제 정보는 S 배열에서 관리. 
	int pos[MAX];  // val 의 heap index 저장. val 범위만큼 필요  

	bool(*comp)(int, int);

	void init(int type)	{ 
		hn = 0; comp = type ? max : min; 
	}

	void swap(int x, int y) { 
		_swap(heap[x], heap[y]); 
		_swap(pos[heap[x]], pos[heap[y]]); // pos 에서의 index 는 heap[] 의 값인 것에 주의
	}
	
	void up(int hidx) {
		for (int c = hidx; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}

	void down (int hidx) {
		// hidx 가 부모이고 그 자식들 입장에서 움직여야 하므로, c 는 hidx * 2 , 즉 왼쪽 자식부터 시작 
		for (int c = hidx * 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}

	void update(int val) {
		int hidx = pos[val];
		up(hidx), down(hidx);
	}

	void erase(int val) {
		int hidx = pos[val];
		swap(hidx, hn--);
		up(hidx), down(hidx);
	}

	void push(int val) {
		heap[++hn] = val;
		pos[val] = hn;
		up(hn); // 할 때에는 현재 hidx 로 하기 때문에 hn 
	}

	void pop() {
		swap(1, hn--);
		down(1);
	}

	int top() { return heap[1]; }

} minpq, maxpq;

□ [U] 회원 참여도 분석1

#include <stdio.h>

typedef unsigned long long ull;
const int MAX = (int)(1e5 + 3);
int N, M;

struct _member { int id; int freq; } mem[MAX];

template <typename _Type> 
void _swap(_Type &x, _Type &y) { _Type temp = x; x = y; y = temp; }

bool max(_member x, _member y) { 
	if (x.freq == y.freq) return x.id > y.id; 
	return x.freq > y.freq; 
}

bool min(_member x, _member y) {
	if (x.freq == y.freq) return x.id < y.id;
	return x.freq < y.freq;
}

struct _priority_queue {
	int hn;
	int pos[MAX]; // id 들의 heap index 기록 
	_member heap[MAX];
	bool(*comp)(_member, _member);

	void init(int type) { hn = 0; comp = type ? max : min; }
	void swap(int x, int y) {
		_swap(heap[x], heap[y]);
		_swap(pos[heap[x].id], pos[heap[y].id]);
	}

	void up(int hidx) {
		for (int c = hidx; c > 1; c /= 2) {
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}

	void down(int hidx) {
		for (int c = hidx * 2; c <= hn; c *= 2) {
			if (c < hn && !comp(heap[c], heap[c + 1])) c++;
			if (comp(heap[c], heap[c / 2])) swap(c, c / 2);
			else break;
		}
	}

	void push(_member newbie) {
		heap[++hn] = newbie;
		pos[newbie.id] = hn;
		up(hn);
	}

	void pop() {
		swap(1, hn--);
		down(1);
	}
	
	void erase(_member member) {
		int hidx = pos[member.id];
		swap(hidx, hn--);
		up(hidx), down(hidx);
	}

	_member top() { return heap[1]; }
} minpq, maxpq;

ull total_frequency() {
	ull sum = 0;

	if (minpq.hn <= 2) return 0;

	for (int m = 1; m <= minpq.hn; m++) 
		sum += minpq.heap[m].freq;
	
	int max_freq = maxpq.top().freq;
	int min_freq = minpq.top().freq;
	
	return sum - max_freq - min_freq;
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);

	minpq.init(0);
	maxpq.init(1);

	int cmd, id, freq;
	
	for (int m = 0; m < M; m++) {
		scanf("%d", &cmd);

		if (cmd == 0) {
			scanf("%d %d", &id, &freq);
			minpq.push({ id, freq });
			maxpq.push({ id, freq });
		}

		if (cmd == 1) {
			if (minpq.hn) {
				_member min_mem = minpq.top();

				minpq.pop();
				maxpq.erase(min_mem);
				printf("%d\n", min_mem.id);
			}
		}

		if (cmd == 2) {
			if (maxpq.hn) {
				_member max_mem = maxpq.top();

				maxpq.pop();
				minpq.erase(max_mem);
				printf("%d\n", max_mem.id);
			}
		}

		if (cmd == 3) {
			ull ans = total_frequency();
			printf("%d\n", ans);
		}
	}
	
	return 0;
}
⚠️ **GitHub.com Fallback** ⚠️