본문 바로가기
Coding/C

[C] Heap의 특정 index 값 수정

by 暻煥 2024. 2. 7.

Heap(Priority Queue)에서 특정 index의 값을 수정하는 방법에 대한 글이다.

​

아래의 내용을 이해하기 위해서는 "배열을 이용한 Heap 구현"에 대해서 알고 있어야 한다.

아래의 링크에는 Heap에 대한 자세한 설명이 있다.

 

 

[자료구조] 힙(heap)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

 

흔히 알고있는 배열을 이용하여 Heap을 구현한 방법은 아래 코드와 같다.

#define MAX_SIZE 100

int heap[MAX_SIZE];
int heap_size = 0;

void HeapInit(void)
{
	heap_size = 0;
}

void GoUp(int index)
{
	int current = index;
	while (current > 0 && heap[current] < heap[(current - 1) / 2])
	{
		int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}
}

void GoDown(int index)
{
	int current = index;
	while (current * 2 + 1 < heap_size)
	{
		int child;
		if (current * 2 + 2 == heap_size)
		{
			child = current * 2 + 1;
		}
		else
		{
			child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current] < heap[child])
		{
			break;
		}

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		current = child;
	}
}

void HeapPush(int value)
{
	if (heap_size + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return;
	}

	heap[heap_size] = value;
	heap_size++;
	GoUp(heap_size - 1);
}

void HeapPop(int* value)
{
	heap_size--;
	*value = heap[0];
	heap[0] = heap[heap_size];
	GoDown(0);
}

 

위 코드를 보면 Push와 Pop연산을 GoDown( ), GoUP( ) 을 통해서 구현했는데,

자세한 이유는 아래에 설명한다.

​

Heap이 동작하는 방법을 먼저 생각해보면,

 

 

Push

→ Heap 이진트리의 제일 뒤쪽에 값을 집어넣고

→ 그 노드가 올라갈 수 있는 최대한으로 "올려"보낸다

 

 

Pop

→ Heap 이진트리의 제일 끝과, 제일 꼭대기를 교환하고
→ 꼭대기로 올라온 노드를 아래로 "내려"보낸다

 

이렇게 일반적으로 구현된 Heap에서 원하는 노드만 값을 변경하고, Heap의 특성을 유지해야 한다

"i 번째로 삽입된 노드의 값 변겅", "id가 특정한 값을 가지는 노드의 값 변경" 같은 상황에 사용하고자 한다.

 

정리하자면, 다음과 같은 문제를 풀고자 한다.

 

배열 a[0], a[1], ...... a[n-1]에 대해서
→ a[i]의 값을 v로 바꾼다
→ a[0], a[1] .......a[n-1] 中 가장 작은 min 값을 출력

 

똑같은 기능을 구현하는 문제는 아래와 같다.

 

14427번: 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 

www.acmicpc.net

 

원하는 동작을 대략적으로 적어보면,

기능1 : 수열의 특정한 index에 해당하는 값이 Heap에 어디에 위치하는지 알아낸다
기능2 : 수열및 heap의 특정한 index에 해당하는 값을 변경한다
기능3 : 항상 최소 값을 출력할 수 있도록, Heap의 구조를 유지한다

위의 3가지 기능을 수행시키면 원하는 것을 수행 할 수 있다.
또한, heap 내부에서 index의 위치를 관리 및  추적 할 수 있는 기능이 필요한다.

먼저 "기능1"을 구현해 보자.

void HeapPush(int value, int idx)
{
	if (heap_size + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return;
	}

	heap[heap_size].value = value;
	heap[heap_size].idx = idx;
	heap_index[idx] = heap_size;
	heap_size++;
	GoUp(heap_size - 1);
}

 

Heap에서 원소를 추가할 때는, 트리의 가장 마지막에 위치시킨다.
그럼, i번 원소를 heap에 넣은뒤, 아무런 이동이 없다면 i번 노드의 index는 heap_size가 된다.
추가한 원소는 위로 트리에서 위로 올려 보내야 하는데, 이때 index도 같이 관리하여 바꿔준다.

void GoUp(int index)
{
	int current = index;
	int parent_idx = (current - 1) / 2;
	while (current > 0 &&  (heap[current].value < heap[(current - 1) / 2].value  ||
		(heap[current].value == heap[(current - 1) / 2].value && heap[current].idx < heap[(current - 1) / 2].idx)) )
	{
		parent_idx = (current - 1) / 2;

		Pii temp = heap[parent_idx];
		heap[parent_idx] = heap[current];
		heap[current] = temp;

		heap_index[ heap[parent_idx].idx ] = parent_idx;
		heap_index[ heap[current].idx ] = current;

		current = parent_idx;
	}
	return;
}

위 source code를 보면 heap_index[x]는 x번째로 삽입된 원소가 heap 에서 어디에 위치하는지 나타낸다.

 

heap[ heap_index[x] ] == "x번째 삽입된 원소"

 

마찬가지로, Pop의 경우에는 트리에서 아래로 내려보내는 함수가 필요한데, 거기에서도 index를 관리하는 기능을 추가하자.

void GoDown(int index)
{
	int current = index;
	while (current * 2 + 1 < heap_size)
	{
		int child;
		if (current * 2 + 2 == heap_size)
		{
			child = current * 2 + 1;
		}
		else
		{
			child =( 
				heap[current * 2 + 1].value < heap[current * 2 + 2].value ||  
				( heap[current * 2 + 1].value == heap[current * 2 + 2].value && 
				heap[current * 2 + 1].idx < heap[current * 2 + 2].idx )
				)
				? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current].value < heap[child].value || 
			(heap[current].value == heap[child].value && heap[current].idx < heap[child].idx))
		{
			break;
		}

		Pii temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		heap_index[heap[current].idx] = current;
		heap_index[heap[child].idx] = child;

		current = child;
	}
}

 

이제 남은 문제는 아래 그림처럼, Heap 자료구조 가운데에 원소의 값이 바뀐 경우이다.

이 경우에도 Heap 구조를 계속 유지시켜야 한다.

방법은 간단한데, Heap에서 원소의 이동은 위방향, 아래방향 둘 중 하나밖에 없다.
즉, 무슨 소리냐 하면, 원소의 이동이 필요한 경우 원소는 한 방향으로만 움직인다.
그러므로, 위로 갔다가 아래로 가거나, 아래로 가다가 위로 가는 경우는 없다.

간단하게 이미 존재하는 함수들로 해결책을 만들면 아래와 같다.

/*
index번째 삽입된 원소의 값을 v로 바꾼다.
*/
void HeapUpdateDirect(int index, int v)
{
	heap[heap_index[index]].value = v;
	GoUp(heap_index[index]);
	GoDown(heap_index[index]);
}

 

비교 연산자가 잘 정의 되어 있다면, 원소는 한 방향으로만 움직이기 때문에 GoUp( ), GoDown( )이 두개가 동시에 반영되지 않는다.

​

예시를 들어 간단히 증명해보이자.

 

값이 변경된 원소 x가 꼭대기로 올라갔다가 하나 내려온 상황을 생각해 보자.
만약 이런 상황이 발생했다면 아래의 조건이 만족되었다는 얘기이다.

(( x<24 ) && (14<x))
즉, 위의 왼쪽 그림에서 처럼 ( 14<24 )가 되어서 애초에 이미 heap 구조를 만족하지 않는 것이 되어버린다.
그러므로, 위로 올라갔다가 아래로 내려가는 상황은 발생 하지 않는다.
반대로 생각해보면, 아래로 내려갔다가 위로 올라가는 상황도 발생하지 않는다.

 

문제

 

 

14427번: 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 

www.acmicpc.net

Source Code

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_SIZE (100009)

typedef struct Pii_t
{
	int value;
	int idx;
}Pii;

Pii heap[MAX_SIZE];
int heap_index[MAX_SIZE];
int heap_size = 0;

void HeapInit(void)
{
	heap_size = 0;
}

void GoUp(int index)
{
	int current = index;
	int parent_idx = (current - 1) / 2;
	while (current > 0 &&  (heap[current].value < heap[(current - 1) / 2].value  ||
		(heap[current].value == heap[(current - 1) / 2].value && heap[current].idx < heap[(current - 1) / 2].idx)) )
	{
		parent_idx = (current - 1) / 2;

		Pii temp = heap[parent_idx];
		heap[parent_idx] = heap[current];
		heap[current] = temp;

		heap_index[ heap[parent_idx].idx ] = parent_idx;
		heap_index[ heap[current].idx ] = current;

		current = parent_idx;
	}
	return;
}

void GoDown(int index)
{
	int current = index;
	while (current * 2 + 1 < heap_size)
	{
		int child;
		if (current * 2 + 2 == heap_size)
		{
			child = current * 2 + 1;
		}
		else
		{
			child =( 
				heap[current * 2 + 1].value < heap[current * 2 + 2].value ||  
				( heap[current * 2 + 1].value == heap[current * 2 + 2].value && 
				heap[current * 2 + 1].idx < heap[current * 2 + 2].idx )
				)
				? current * 2 + 1 : current * 2 + 2;
		}

		if (heap[current].value < heap[child].value || 
			(heap[current].value == heap[child].value && heap[current].idx < heap[child].idx))
		{
			break;
		}

		Pii temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		heap_index[heap[current].idx] = current;
		heap_index[heap[child].idx] = child;

		current = child;
	}
}

void HeapPush(int value, int idx)
{
	if (heap_size + 1 > MAX_SIZE)
	{
		printf("queue is full!");
		return;
	}

	heap[heap_size].value = value;
	heap[heap_size].idx = idx;
	heap_index[idx] = heap_size;
	heap_size++;
	GoUp(heap_size - 1);
}

Pii HeapTop(void)
{
	return heap[0];
}

void HeapPop(int* value)
{
	heap_size--;

	*value = heap[0].value;
	heap[0] = heap[heap_size];
	
	GoDown(0);
}

void HeapUpdateDirect(int index, int v)
{
	heap[heap_index[index]].value = v;
	GoUp(heap_index[index]);
	GoDown(heap_index[index]);
}

int main(int argc, char* argv[])
{

	int N;
	//freopen("sample_input.txt", "r", stdin);
	scanf("%d", &N);

	HeapInit();

	for (int i = 0; i < N; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		HeapPush(tmp, i);
	}

	int num_query;
	scanf("%d", &num_query);

	while (num_query--)
	{
		int type;
		scanf("%d", &type);
		switch (type)
		{
		case 2:
			printf("%d\n", HeapTop().idx + 1);
			break;
		case 1:
			int i, v;
			scanf("%d %d", &i, &v);
			HeapUpdateDirect(i - 1, v);
			break;
		default:
			break;
		}
	}

	return 0;
}

 

 

'Coding > C' 카테고리의 다른 글

[C] Priority Queue  (0) 2025.11.16
[C] Quick Sort  (0) 2025.11.15
[C] AVL Tree  (0) 2024.02.05
[C] RB Tree 구현  (1) 2024.02.05

관련글

티스토리툴바