[자료구조] 힙(heap)에 대해서 알아보자

[자료구조] 힙(heap)에 대해서 알아보자

300x250

힙은 완전 이진 트리의 형태를 갖고 있으며 우선 순위 큐를 해결하기 위해 만들어진 자료구조입니다.

(앞서 트리에 대한 이해가 필요합니다.)

완전 이진 트리

이진 트리는 자식 노드의 개수를 최대 2개로 갖는 트리를 의미하며 이 조건을 만족하면서 왼쪽부터 차례대로 채워지는 트리 를 완전 이진 트리라고 합니다.

우선순위 큐

가장 우선순위가 높은 데이터를 추출

리스트를 이용하여 차례대로 순회하면서 가장 큰 값을 추출하는 방식으로 우선순위큐를 구현할 수 있지만 이러한 경우 추출 시 시간복잡도가 O(N)이 되기 때문에 리스트의 삽입될 값이 많다면 비효율적인 방식이라고 할 수 있습니다.

힙은 데이터 삽입과 추출과정 모두 시간복잡도 O(logN)을 갖습니다.

힙은 다음과 같이 두 가지로 분류할 수 있습니다.

부모의 값이 항상 자식의 값보다 작은 경우: 최소 힙

최소 힙을 만족하는 트리

위의 트리에서 9의 자식노드로 1이 삽입되면 어떻게 될까?

최소 힙조건을 만족하지 않는 트리

위와 같은 과정을 통해 작은 값을 부모노드와 순차적으로 교환하여 가장 작은 값을 루트 노드로 보냅니다.(상향식)

값을 추출한 경우 가장 마지막 노드를 루트 노드로 보내고 힙조건을 만족시키도록 재구성합니다.(하향식)

최소 힙정렬(코드 구현)

import heapq #파이썬은 heapq모듈을 지원합니다. Nums=list(map(int,input().split())) def Min_heap(nums): heap=[] for i in nums: heapq.heappush(heap,i) sort_nums=[] for i in range(len(heap)): sort_nums.append(heapq.heappop(heap)) #추출한 데이터를 새로운 리스트에 추가 return sort_nums print(Min_heap(Nums))

부모의 값이 항상 자식의 값보다 큰 경우: 최대 힙

파이썬의 heapq모듈에서 기본적으로 지원하는 힙은 최소힙이기 때문에 데이터를 삽입할 때와 값을 새로 담을 때 ( - )를 사용하여 최대 힙 정렬을 할 수 있습니다.

최대 힙 정렬(코드구현)

import heapq Nums=list(map(int,input().split())) def Min_heap(nums): heap=[] for i in nums: heapq.heappush(heap,-i) sort_nums=[] for i in range(len(heap)): sort_nums.append(-heapq.heappop(heap)) return sort_nums print(Min_heap(Nums))

반응형

from http://lbdiaryl.tistory.com/152 by ccl(A) rewrite - 2021-09-08 13:26:38