[구현]min, maxheap

문득 내가 즐겨쓰는 라이브러리들이 몇개 있는데,

걔네를 쓰지 말라하면, 어떻게 하나.. 고민하다

후다닥 구현 정리중..

 

min/max heap은 알고리즘에서는 '우선순위 큐'로 더 많이 이용되고 있다.

간단히 소개하자면,

min heap이라면,

2진 트리 형태로, 무조건 parent노드가 child노드보다 더 작아야한다.

그래서, 최상의 root노드는 항상 최소의 값이 위치한다.

 

파이썬에서는 heapq로 사용하는데,

life-of-h2i.tistory.com/17

[Python]Minheap

그건 요기

 

이번엔 min heap구현이다. heap은 모습은 트리지만, 사실은 배열로 구현을 한다.

그래서, heap이 아닌 상태 --> tree라고 이야기하겠다.

 

한가지 더, heap은 부모노드 index를 i라할때, i*2+1, i*2+2 (i가 0부터 시작) 이라는 특징을 갖는다.

 

구현 방법은 다음과 같다.

[heapify]

현재 노드를 root로 하는 sub-tree가 heap이 되도록 정리한다.

방법:

1. 자식노드와 비교하며, 만약 자식노드보다 크면 switch시킨다.

2. 자식 노드의 level에서도 마찬가지를 진행하며, 더이상 변화가 없으면, heap이 만들어진것이다. 

 

[삽입]

원소를 삽입했을때 전체가 heap을 유지해야한다.

1. 일단 삽입할 원소를 배열 마지막에 append한다.

2. tree의 level을 하나씩 올라가면서 heapify를 진행한다. (root까지)

 

[삭제]

1. root를 삭제한다.

2. tree 의 전체 level에 대해서 heapify를 진행한다.

 

def heapify(q,i):
    n=len(q)
    cur_root=i
    cur_val=q[cur_root]
    left=i*2+1
    right=i*2+2
    flag=0
    if left<n and q[cur_root]>q[left]:#루트보다 더작을때
        q[cur_root],q[left]=q[left],q[cur_root]
        flag=left
    elif right<n and q[cur_root]>q[right]:
        q[cur_root],q[right]=q[right],q[cur_root]
        flag=right
    if cur_val!=q[cur_root]:
        heapify(q,flag)
    return q
        
def build_heap(q):
    n=len(q)
    for i in range(n//2-1,-1,-1):
        q=heapify(q,i)
    return q
    

class pq:
    def __init__(self,list):
        self.q=list
        self.length=len(self.q)
    def insert(self,element):
        self.q.append(element)
        self.q=build_heap(self.q)
        print(self.q)
    def pop(self):
        print(self.q.pop(0))
        self.q=build_heap(self.q)