💡 파이썬에서의 힙 구현 방법

파이썬에서는 heapq 라이브러리를 통해 힙을 굉장히 간단하게 구현할 수 있다. 먼저 heapq를 import해주어야 한다.

import heapq

힙에서 가장 중요한 pop과 push 키워드는 다음과 같다.

heapq.heappush(배열, 추가할 원소)  # push
heapq.heappop(배열)  # pop

파이썬의 heapq라이브러리는 기본적으로 최소 힙을 구현한다. 따라서 최대 힙을 만들기 위해서는 push를 할 때 튜플을 이용해 추가해야 한다. 예를 들어, 3을 추가 하고 싶다면 (-3, 3)을 추가하는 식으로 추가하고자 하는 원소에 음수를 취해서 heapq의 최소 힙 정렬을 이용하는 것이다. 나중에 pop을 할 때에는 튜플의 첫번째 인덱스의 값을 꺼내야 하므로 heapq.heappop(배열)[1]로 꺼내면 된다.

📝 소스코드

import sys, heapq
input = sys.stdin.readline

# 힙 배열 생성
heap = []

def opr(heap, x):
    if x==0:
    	# 최대 힙 pop
        if heap:
            print(heapq.heappop(heap)[1])
        # 힙 배열이 비어있으면
        else:
            print(0)
    # 원소를 넣을 때 -를 붙인 원소를 함께 넣음
    elif x>0:
        heapq.heappush(heap, (-x, x))

N = int(input())
for _ in range(N):
    x = int(input())
    opr(heap, x)

💡 C언어로 구현한 힙

파이썬의 장점이자 단점은 라이브러리가 너무 편하게 되어있어서(특히 자료구조같은 경우) 힙을 구현하는 코드를 작성하라고 하면 까먹어서 작성을 못할 것 같다는 것이다. 밑의 코드는 C언어로 구현한 힙이다. 힙정렬을 할 때에는 아래에서부터 위로 올라가며 정렬하는 방식과 위에서부터 아래로 정렬하는 방식이 있다. 여기서는 UpHeap, DownHeap으로 표현했다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int heap[100];
int n = 0;

void InsertItem(int key);
int RemoveMax();
void UpHeap(int i);
void DownHeap(int i);
void PrintHeap();

int main()
{
	char opr;
	int key;
	while (1)
	{
		scanf("%c", &opr);
		if (opr == 'i')
		{
			scanf("%d", &key);
			InsertItem(key);
			printf("0\n");
		}
		if (opr == 'd')
			printf("%d\n", RemoveMax());
		if (opr == 'p')
			PrintHeap();
		if (opr == 'q')
			break;
		getchar();
	}
	return 0;
}

// 힙에 원소를 넣는 함수 push에 해당
void InsertItem(int key)
{
	n++;
	heap[n] = key;
	UpHeap(n);
}

// 최대 힙을 pop하는 함수
int RemoveMax()
{
	int max_key;
	max_key = heap[1];
	heap[1] = heap[n];
	n--;
	DownHeap(1);
	return max_key;
}

// 아래에서부터 위로 힙정렬 수행하는 함수
void UpHeap(int i)
{
	int temp;
	while (i > 1)
	{
		if (heap[i] > heap[i / 2])
		{
			temp = heap[i];
			heap[i] = heap[i / 2];
			heap[i / 2] = temp;
			i = i / 2;
		}
		else
			break;
	}
}

// 위에서부터 아래로 힙정렬하는 함수
void DownHeap(int i)
{
	int temp, bigger_index;
	while (2*i <= n)
	{
		bigger_index = 2 * i;
		if (n>=2*i+1 && heap[bigger_index] < heap[2 * i + 1])
			bigger_index = 2 * i + 1;

		if (heap[i] > heap[bigger_index])
			break;

		temp = heap[i];
		heap[i] = heap[bigger_index];
		heap[bigger_index] = temp;

		i = bigger_index;
	}
}

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