Algorithms-[Heap]

오늘은 heap에 대해서 알아보겠다.

우선 heap을 한단어로 설명하자면 규칙을 가진 이진트리이다. 이진트리가 무엇이냐면 각각의 노드가 최대 2개의 자식노드를 가진 트리를 말한다. 자식노드는 왼쪽 자식과 오른쪽 자식노드로 나뉜다. 다음으로 규칙으로는 최소힙과 최대힙이 있는데, 최소힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙을 말하고 최대힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 말한다. 

<https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/>

위 그림처럼 두개의 자식노드만 가지면서 왼쪽 자식은 부모노드의 index*2 위치에 넣고, 오른쪽 자식은 부모노드의 index*2+1위치에 넣는다. 우선 힙은 첫번째 인덱스를 0으로 하면 계산이 복잡해져서 1로 두고 10을 인덱스 1위치에 넣는다. 다음으로 15는 1*2위치인 인덱스 2에 넣고, 30은 1*2+1위치인 인덱스3에 넣는다. 이렇게 삽입을 반복하면서 최소힙, 최대힙 규칙을 유지하기위해 삽입후에 부모노드와의 크기비교를 통해 노드의 값을 바꾸면 된다. 

이렇게 구현한 힙의 특징은 아래와 같다.

•  여러 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있다.
• 힙은 일종의 반정렬 상태를(규칙만 만족하면 완전정렬이 아니어도됨) 유지한다.
• 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
• 힙 트리에서는 중복된 값을 허용한다.

이러한 힙을 파이썬에서는 구현하기가 쉽다. 왜냐면 모듈과 함수가 있기 때문이다.

import heapq

heap=[]
tmp=int(input())
heapq.heappush(heap,tmp)
heapq.heappop(heap)

우선 모듈을 import하고 heap자료구조를 만든다음 heapq.heappush(heap,tmp)를 하면 heap안에 tmp가 최소힙 규칙에 맞게 들어간다. 다음으로 heappop을 사용하면 제일 최솟값을 pop하고 출력해준다. 이때 heap에 원소가 없으면 에러가 난다. 기본적으로 이렇게 최소힙을 구현해주기 때문에 최대힙을 구현하려면 입력값을 음수로 바꾼뒤에 heap.push를 통해 힙을 생성하고 마지막에 heappop을 통해 출력해줄 때 출력값만 다시 양수로 바꿔주면 최대힙과 동일한 값을 출력하게 된다. 힙을 이용한 삽입,삭제의 시간복잡도는 log(n)으로 가장 빠르다!!