힙의 조건
1. 완전 이진 트리
2. 힙 특성 : 모든 노드는 값을 갖고, 자식 노드(들) 값 보다 크거나 같다.
* 리스트가 A[0]부터 시작된다면, A[k]의 자식은 A[2*k+1]과 A[2*k+2], A[k]의 부모 노드는 A[(k-1)//2]이 된다.
스며 오르기 (percolateUp) : 원소 삽입
스며 내리기 (percolateDown) : 원소 삭제, 힙 생성
힙의 구현 (Python)
class Heap:
def __init__(self, *args):
if len(args) != 0:
self.__A = args[0] # 파라미터로 온 리스틓
else:
self.__A = []
def percolateUp(self, i):
parent = (i - 1) // 2
if i > 0 and self.__A[i] > self.__A[parent]:
self.__A[i], self.__A[parent] = self.__A[parent], self.__A[i]
self.percolateUp(parent)
def percolateDown(self, i):
left = 2 * i + 1
right = 2 * i + 2
if left <= len(self.__A) - 1:
child = left
if right <= len(self.__A) - 1 and self.__A[right] > self.__A[left]:
child = right
if self.__A[i] < self.__A[child]:
self.__A[i], self.__A[child] = self.__A[child], self.__A[i]
self.percolateDown(child)
def insert(self, x):
self.__A.append(x)
self.percolateUp(len(self.__A) - 1)
def deleteMax(self):
if self.isEmpy():
return None # max값을 리턴해 주어야 하므로, 값이 없는 경우의 예외를 처리해 주어야 함!
self.__a[0], self.__a[-1] = self.__a[-1],self.__a[0]
max = self.__a.pop()
self.percolateDown(0)
return max
def buildHeap(self):
for i in range((len(self.__A) - 2) // 2, -1, -1):
self.percoltaeDown(i)
def max(self):
return self.__A[0]
def isEmpty(self):
return len(self.__A) == 0
def clear(self):
self.__A = []
def size(self):
return len(self.__A)비재귀로 힙 구현하기(push, pop)
# 비재귀로 힙 구현하기
heap = [1,3,4,6,7,9]
def push(heap, x):
heap.append(x)
current = len(heap)-1
# 현재 원소가 루트에 도달하면 종료한다.
while current > 0:
parent = (current-1)//2
if heap[parent] > heap[current]:
heap[parent], heap[current] = heap[current], heap[parent]
current = parent
else: break
push(heap, 2); print(heap) # [1,3,2,6,7,9,4]
push(heap, 5); print(heap) # [1,3,2,6,7,9,4,6]
heap = [1,3,2,6,7,9,4,6]
def pop(heap):
if not heap: return None
elif len(heap) == 1: return heap.pop()
heap[0], heap[-1] = heap[-1], heap[0]
retItem = heap.pop()
current, child = 0, 1
while child <= len(heap)-1:
right = child + 1
if right <= len(heap)-1 and heap[child] > heap[right]:
child = right
if heap[current] > heap[child]:
heap[current], heap[child] = heap[child], heap[current]
current = child
child = current*2+1
else: break
return retItem
print(pop(heap)) # 1
print(pop(heap)) # 2
print(heap) # [3,5,4,6,7,9]
// C언어로 구현한 힙(우선순위 큐)
#define parent(i) (i-1)//2
#define left(i) 2*i+1
#define right(i) 2*i+2
#include <stdio.h>
#include <stdlib.h>
typedef struct Heap{
int capacity;
int size;
int* arr;
}Heap;
Heap* createHeap(int capacity){
Heap* newHeap = (Heap*)malloc(sizeof(Heap));
newHeap->capacity = capacity;
newHeap->size = 0;
newHeap->arr = (int*)malloc(sizeof(int)*capacity);
return newHeap;
}
void exchange(int arr[],int i,int j){
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// percolateDown
// Time complexity : O(log n)
void max_heapify(Heap* heap, int i){
if(left(i) <= heap->size-1){
int child = left(i);
if(right(i) <= heap->size-1 && (heap->arr[child] < heap->arr[right(i)])){
child = right(i);
}
if(heap->arr[i] < heap->arr[child]){
exchange(heap->arr, i, child);
max_heapify(heap, child);
}
}
}
void min_heapify(Heap* heap, int i){
if(left(i) <= heap->size-1){
int child = left(i);
if(right(i) <= heap->size-1 && (heap->arr[child] > heap->arr[right(i)])){
child = right(i);
}
if(heap->arr[i] > heap->arr[child]){
exchange(heap->arr, i, child);
max_heapify(heap, child);
}
}
}
// buildHeap
// Time complexity : O(n)
void build_max_heap(Heap* heap){
for(int i = (heap->size-2)/2; i >= 0; i--)
max_heapify(heap, i);
}
void build_min_heap(Heap* heap){
for(int i = (heap->size-2)/2; i >= 0; i--)
min_heapify(heap, i);
}
// percolateUp
void percolateUp(Heap* heap, int i, char* mod){
if(mod == "max"){
while(i>0 && heap->arr[parent(i)] < heap->arr[i]){
exchange(heap->arr, i, parent(i));
i = parent(i);
}
}
else if(mod == "min"){
while(i>0 && heap->arr[parent(i)] > heap->arr[i]){
exchange(heap->arr, i, parent(i));
i = parent(i);
}
}
}
// insertion
// Time complexity : O(log n)
void insert(Heap* heap, int key){
if(heap->size == 0){
heap->arr[0] = key;
heap->size += 1;
}
else{
heap->arr[++heap->size] = key;
percolateUp(heap, heap->size, "max");
}
}
// get
// Time complexity : O(1)
int get_max(Heap* heap){
// max_heap일 때 유효함
return heap->arr[0];
}
// extract
// Time complexity : O(log n)
int extract_max(Heap* heap){
if(heap->size < 1) return 99;
int max = heap->arr[0];
heap->arr[0] = heap->arr[heap->size-1];
max_heapify(heap, 0);
return max;
}
int main(int argc, char* argv[]){
Heap* heapq = createHeap(10);
insert(heapq, 5);
insert(heapq, 1);
insert(heapq, 3);
insert(heapq, 2);
insert(heapq, 6);
for(int i = 0; i < heapq->size; i++)
printf("%d ", extract_max(heapq));
return 0;
}
파이썬 heapq 모듈
heapq는 최소 힙(min-heap) 으로 구현, 항상 가장 작은 값이 루트에 위치
heapq.heapify(iterable)
- 리스트를 힙 구조로 변환
- O(n) 시간복잡도
heapq.heappush(heap, item)
- 힙에 item을 추가
- O(log n)
heapq.heappop(heap)
- 가장 작은 원소(루트 노드) 를 제거하고 반환
- O(log n)
import heapq
data = [3, 1, 5, 2, 4]
heapq.heapify(data)
print(data)
# [1, 2, 5, 3, 4] - 내부적으로 최소 힙 구조를 가짐
heapq.heappush(data, 0)
print(data) # [0, 1, 5, 3, 4, 2]
min_item = heapq.heappop(data)
print(min_item) # 0